19. Remove Nth Node From End of List https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/ 删除链表的倒数第 N 个结点
例如 给出列表: 1->2->3->4->5, and n = 2.
删除倒数第二个结点后变为: 1->2->3->5
题目限定 n 总是有效的, 且要求我们尽量用一次遍历解决问题
数据结构: Linked List
算法技巧: Tow Pointers(辅助指针)
- // 总体思路是设置两个指针 A 和 B,A 指向 head 结点, B 先走 2 步指向 2 结点. 然后 AB 指针同时向后移动, 直到 B 指针为空, 这时 A 指针指向的是倒数第三个结点 2, 执行常规删除动作
- class Solution {
- public:
- ListNode* removeNthFromEnd(ListNode* head, int n) {
- if(!head->next)
- return NULL;
- ListNode* pre = head;
- ListNode *cur = head;
- //B 指针先走 2 步
- for(int i = 0; i <n; ++i)
- cur = cur->next;
- if(!cur)
- return head->next;
- //AB 指针同时向后移动, 直到 B 指针为空
- while(cur->next)
- {
- cur = cur->next;
- pre = pre->next;
- }
- // 常规删除结点操作
- pre->next = pre->next->next;
- return head;
- }
- };
206. Reverse Linked List https://leetcode.com/problems/reverse-linked-list/description/ 反转单链表
使用到的数据结构: List
使用到的算法技巧: dummy node(虚拟结点)
- // 引入虚拟结点 dummy, 让 reverse 过程更好理解
- // 反转流程: 1->2->3->4->5->NULL
- //step1 dummy node(-1)->1->2->3->4->5->NULL cur(1)
- //step2 dummy node(-1)->2->1->3->4->5->NULL cur(1)
- //step3 dummy node(-1)->3->2->1->4->5->NULL cur(1)
- //step4 dummy node(-1)->4->3->2->1->5->NULL cur(1)
- //step5 dummy node(-1)->5->4->3->2->1->NULL cur(1)
- class Solution {
- public:
- ListNode* reverseList(ListNode* head) {
- if(!head) return head;
- ListNode *dummy = new ListNode(-1);
- dummy->next = head;
- ListNode *cur = head;
- while(cur->next)
- {
- ListNode* tmp = cur->next;
- cur->next = tmp->next;
- tmp->next = dummy->next;
- dummy->next = tmp;
- }
- return dummy->next;
- }
- };
来源: http://www.jianshu.com/p/a73a2d9f56a5