题目
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
- 大意：给定一个链表和一个数n，从一个链表中删去从后变数的第n个节点，比如1->2->3->4->5, n = 2.处理完后为1->2->3->5.。注意给定的n都是有效的，尝试用一遍遍历完成。
思路0
python投机取巧的做法，将链表遍历转为数组，直接删除第-n个元素（注意因为从后数第一个节点index为-1，则后数第n个节点index为-n）
代码：(python)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x <!--more--> # self.next = None class Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ p = head l = [] while p.next != None: l.append(p.val) p = p.next l.append(p.val) del l[-n] return l |
思路1
题设是单链表，不方便从后遍历。而从前边遍历判断是尾节点的方法只能是当前指向的节点的next节点是NULL。我们如果定义两个指针，分别指针，第一个指向第0个节点，第二个指针第n个节点，两个指针同时向后遍历，当尾节点的时候，第一个指针所指向的节点正好是从后数第n+1个节点，这时只要将第一个指针的.next修正为.next.next即可。
特殊情况是，注意到题设n总是有效的，所以如果第n个(从0开始数)节点不存在，则一定是链表只存在n个节点，只需要删除第0个节点即可（返回head.next）。
|
1 2 3 4 5 6 7 8 9 |
比如n=3： 开始第一次循环后： n0->n1->n2->n3->......n(n-3)->n(n-2)->n(n-1)->n(n) ^ ^ 遍历后： n0->n1->n2->n3->......n(n-3)->n(n-2)->n(n-1)->n(n) ^ ^ 此时只需要删除第一个指针后边的元素即可。 |
代码(python)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ p1 = p2 = head for i in range(n): p2 = p2.next if not p2: return p1.next while p2.next: p1 = p1.next p2 = p2.next p1.next = p1.next.next return head |
代码(c++)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode * p1 = head; ListNode * p2 = head; for(int i = 0; i < n; i++) { p2 = p2->next; } if(!p2) { return head->next; } while(p2->next) { p1 = p1->next; p2 = p2->next; } p1->next = p1->next->next; return head; } }; |
参考:
《3 short Python solutions》(https://leetcode.com/discuss/37149/3-short-python-solutions)