[关闭]
@smilence 2016-05-04T23:14:21.000000Z 字数 2361 阅读 4925

Chapter 2 Linked Lists

除特别说明外,本文提到的list特指singly linked list

  1. //Definition for singly-linked list.
  2. struct ListNode {
  3. int val;
  4. ListNode *next;
  5. ListNode(int x) : val(x), next(NULL) {}
  6. };

1.list STL类(双向list)的主要函数:
push_back(const val_type& val),pop_back();
erase(iterator it),clear();
val_type &front(), val_type &back()

2.Singly linked list的基本操作

所有操作务必注意边界条件( curr == headcurr == tailcurr == NULL)
凡是修改list的操作,只需考虑 1. 谁的next指针会受到影响,则需要修正 2.删除trash指针

  1. void delNode(ListNode *prev){
  2. ListNode *curr = prev->next;
  3. prev->next = prev->next->next;
  4. delete curr;
  5. }

注:对于非只读操作,定义prev并考察curr->val,可能不如考察prev->next->val来的简洁。

3.Dummy Node

对于涉及head节点的操作,不如ListNode *dummy = new ListNode(0); dummy->next = head;;使针对head节点的处理与其他节点一致。最后返回dummy->next作为头指针即可。

e.g. Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

4.Runner technique
对于寻找list某个特定位置的问题,不妨:ListNode *chaser = head, *runner = head; chaserrunner以不同速率遍历,runner到达tail时,返回chaser

e.g.1 Find the middle point of the linked list

  1. ListNode *midpoint( ListNode *head){
  2. ListNode *chaser = head, *runner = head;
  3. while( runner->next && runner->next->next ){
  4. chaser = chaser->next;
  5. runner = runner->next->next;
  6. }
  7. return chaser;
  8. }

e.g.2 Find the kth to last element of a singly linked list.
e.g.3 Given a circular linked list, return the node at the beginning of the loop.
e.g.4 Given a list, rotate the list to the right by k places, where k is non-negative. (Leetcode: Rotate List)

模式识别

1.在遍历Linked list时,注意每次循环内只处理一个或一对节点。

e.g.Reverse the linked list and return the new head.

  1. ListNode *reverse( ListNode *head ){
  2. //Of course, it can also be done by recursion/stack
  3. ListNode *prev = NULL;
  4. ListNode *next = head->next;
  5. while(head){
  6. head->next = prev;
  7. prev = head;
  8. head = next;
  9. next = next->next;
  10. }
  11. return prev;
  12. }

2.Swap Node 问题
根据Rule No.2, 交换两个节点,不存在删除,两个节点的prev节点,以及两个节点的next指针,分别受到影响。
因此可以 a. 先交换两个prev节点的next指针的值 ; b. 再交换这两个节点的next指针。
无论这两个节点的相对位置和绝对位置,以上处理总是成立。只是可能可以进一步缩写代码。

e.g. Given a linked list, swap every two adjacent nodes and return its head.( Leetcode: Swap Nodes in Pairs)
http://paste.ofcode.org/pWMacnKCY9xYxJ5JKtPzLn

3.处理两个长度未必相等的linked list的问题,循环的条件一般为 while( l1 && l2 ) ,再处理剩下非NULL 的list。

e.g Merge two sorted linked lists and return it as a new list.(Leetcode: Merge Two Sorted Lists)

4.如果对靠前节点的处理必须在靠后节点之后,即倒序访问问题,(前面节点的解依赖于后面节点的解),则可视为recursion问题,或可以用stack等效解决。

e.g.1 Traverse the linked list reversely.

  1. void traverse(ListNode *head){
  2. if( head == NULL )
  3. return;
  4. traverse(head->next);
  5. visit(head);
  6. }

e.g.2 Given input ( 7->1->6 ) + ( 5->9->2 ), output 2->1->9. // 无需递归,因为靠前节点不依赖于靠后节点
Follow up, Given input ( 6->1->7 ) + ( 2->9->5 ), output 9->1->2. //用递归或stack处理,因为靠前节点的结果依赖靠后节点的处理

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注