Chapter 2 Linked Lists

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

//Definition for singly-linked list.
struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

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 == head，curr == tail 或 curr == NULL)
凡是修改list的操作，只需考虑 1. 谁的next指针会受到影响，则需要修正 2.删除trash指针

void delNode(ListNode *prev){
    ListNode *curr = prev->next;
    prev->next = prev->next->next;
    delete curr;
}

注：对于非只读操作，定义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; chaser与runner以不同速率遍历，runner到达tail时，返回chaser。

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

ListNode *midpoint( ListNode *head){
    ListNode *chaser = head, *runner = head;
    while( runner->next && runner->next->next ){
        chaser = chaser->next;
        runner = runner->next->next;
    }
    return chaser;
}

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.

ListNode *reverse( ListNode *head ){
    //Of course, it can also be done by recursion/stack
    ListNode *prev = NULL;
    ListNode *next = head->next;
    while(head){
        head->next = prev;
        prev = head;
        head = next;
        next = next->next;
    }
    return prev;
}   

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.

void traverse(ListNode *head){
    if( head == NULL )
        return;
    traverse(head->next);
    visit(head);
}

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处理，因为靠前节点的结果依赖靠后节点的处理