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

//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()

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

3.Dummy Node

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

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)

### 模式识别

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 问题

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

• 私有
• 公开
• 删除