Given a linked list, remove the nth node from the end of list and return its head.
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个数,要求只能遍历一次,所以不能先遍历一次看共有多少个元素再重新遍历到size-n。
用两个指针,一个指针先走n步,此时如果把尾看成头,则相当于走到了倒数第n+1个数的位置。另一个指针从这时候开始,两个指针同时移动,当第一个指针移动到尾节点的时候,第二个指针的next就是要被删除的节点。
需要注意的是,如果第一个指针走完n步已经到尾节点,说明删除的就是head,返回head->next即可。
O(n)
/** * 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) { if (head -> next == NULL || head == NULL) return NULL; ListNode* p = head; for (int i = 0; i < n; i++) { p = p -> next; } if (p == NULL) return head -> next; else { ListNode* q = head; while(p->next != NULL) { q = q -> next; p = p -> next; } ListNode* temp = q -> next; q -> next = temp -> next; delete temp; } return head; } };