第五部分：链表

算法面试指南

5.1 知识与技巧解析

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

2.linked list的基本操作
对节点操作，无非就是修改next指针，如果是双向链表，还有prev指针。也决定了节点之间的相对位置，基本就是决定了这个linked list。

所有操作务必注意边界条件( curr == head，curr == tail 或 curr == NULL)
凡是修改list的操作，只需考虑 1. 谁的next指针会受到影响，则需要修正 （毕竟绝大多数的问题，next指针就是node唯一重要的member variable) 2.删除trash指针

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

3.Dummy Node

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

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。(这个办法实际上是解决单向链表无法随机访问，所以只能用walk through来确定相对位置， 毕竟绝对位置用计数就可以了)

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) (拆分成两个问题：找到拆分点，拆分)

5.2 模式识别

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. 1->2->3->4 => 3->4->2->1
无论这两个节点的相对位置和绝对位置，以上处理总是成立。只是可能可以进一步缩写代码。

e.g. Given a linked list, swap every two adjacent nodes and return its head.( Leetcode: Swap Nodes in Pairs)
Given 1->2->3->4, you should return the list as 2->1->4->3.每个节点的next指针都会发生变化。

ListNode *swapPairs(ListNode *head) {
    if(!head)    return head; // 注意边界条件
    // swap之后head可能发生变化
    ListNode *dummy = new ListNode(0); 
    dummy->next = head;
    // 初始化    
    ListNode *prev1 = dummy;
    ListNode *node1 = head, *node2 = head->next;
    // 一次循环只处理这一个pair
    while(node1 && node1->next){
        node2 = node1->next;
        // 这时候只需要考虑 (prev1, node1) 和 (node1 , node2) 相互独立的两对
        // swap the "next" of prev nodes;
        ListNode *tmp = prev1->next; // =node1
        prev1->next = node1->next; // = node2
        node1->next = tmp; // = node1
        //swap the "next" of current nodes;
        tmp = node1->next; // = node1
        node1->next = node2->next;
        node2->next = tmp; // = node1
        // 也可以写 prev2, node2, 然后再node1 = prev2 代入解方程
        // 可以根据 comment来缩写
        prev1 = node1;
        node1 = prev1->next; // 这里不写node1->next, 因为不想纠缠这里面的关系，从新的prev1出发即可
    }
    return dummy->next;
}

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

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;
    // Linked List 特别的地方
    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处理，因为靠前节点的结果依赖靠后节点的处理, f(n) = Q( V(n), f(n-1) ), 这里的f(n)是进位 + linkedList的一个bundle (转换成string，先reverse再相加的空间复杂度是相同的）

e.g. A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.

Node {
 T value, 
 Node *next,
 Node *random,
}

Deep Copy: 建立一个hashtable来记录从oldNode到newNode的mapping: table[oldNode] = newNode, 然后去遍历老的数据结构（既然是copy，至少是O(n)），建立并且利用这个mapping;

 RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map< RandomListNode *, RandomListNode *> table;
        RandomListNode *old = head;
        RandomListNode *dummy = new RandomListNode(0);
        RandomListNode *new = dummy;
        while(old){
            new->next = new RandomListNode(old->label);
            table[old] = new->next; // old->next = new->next
            old = old->next;
            new = new->next;
        }
        new = dummy->next;
        old = head;
        while(old){
            if(old->random)
                new->random = table[old->random];
            old = old->next;
            new = new->next;
        }
        return dummy->next;
    }

这个问题一定要两次遍历，因为既可能依赖于前面的又可能依赖于后面的计算结果：反过来想，两次遍历是一个解决这类问题的一个思路

Shallow copy verus Deep copy (给所有的member variable也建立一份copy)
cloneGraph 也是类似的， 建立mapping的同时，利用这个mapping，类似于DP的思想

    GraphNode *cloneGraph(GraphNode *node, unordered_map<GraphNode *,GraphNode *>& table){
        if(!node)   return NULL;
        if(table.count(node)>0) return table[node];
        GraphNode *newNode = new GraphNode(node->label);
        table[node] = newNode;
        for(auto it = (node->neighbors).begin(); it != (node->neighbors).end(); ++it)
            (newNode->neighbors).push_back(cloneGraph(*it,table));
        return newNode;
    }

考虑时间复杂度的时候要有全局概念，比如建立cache的空间复杂度是O(n)，那么就不用去考虑递归的空间开销