Linked List 总结

2016-03-21

前言

最近把leetcode的linked list专题刷完了，我感觉收获很多，也看了很多他人的代码，对单链表的理解又更深了一步，所以写篇博文来总结一下，同时也方便自己以后复习。

leetcode上的链表节点定义如下：

struct ListNode{
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};

设置哨兵节点

哨兵（sentinel）是个哑元节点（dummy node），可以简化边界条件，使代码更紧凑，但对速度并没有什么帮助。

单链表反转

使用三个指针完成单链表的反转。

ListNode *p, *q, *temp;
p = root;
q = root->next;
p->next = NULL;   
while(q != NULL){
    temp = q->next;
    q->next = p;
    p = q;
    q = temp;
}

单链表并归排序（merge sort）

采用递归的方法，Linked List中的很多问题都可以采用递归的方法。比较直接。

伪代码：

ListNode* sortList(ListNode *head){
    if (head == NULL || head->next == NULL)
    return head;
}
merge(sorList(head), sortList(1/2 链表的位置);

其中 merge(a, b); 是合并两个有序链表。
1/2 链表的位置：可以采用两个指针，一个一步/次，一个两步/次，从而得到链表1/2的位置。

代码：

//链接两个有序链表
ListNode* merge(ListNode *a, ListNode *b){
    ListNode *head, *cur;
    ListNode dummy(0);
    head = cur = &dummy;
    
    while(a!=NULL && b!=NULL){
        if (a->val > b->val){
            cur->next = b;
            b = b->next;
            cur = cur->next;
        }
        else{
            cur->next = a;
            a = a->next;
            cur = cur->next;
        }
    }
    cur->next = (a==NULL)? b : a;
    return head->next;
    }
    
ListNode* sortList(ListNode* head) {
        ListNode *a, *b;
    if(head == NULL || head->next == NULL){
        return head;
    }
    a=b=head;
    while(b->next && b->next->next){
        a = a->next;
        b = b->next->next;
    }
    b = a->next;
    a->next = NULL;
    
    return merge(sortList(head),sortList(b));
}

判断链表是否有环并找到环入口

判断是否有环：
slow指针一次走一步：slow = slow->next;
fast指针一次走两步: fast = fast->next->next;

若两者相遇： fast == slow 则存在环。

若(fast->next == NULL || fast == NULL) 则不存在环。

找环的入口:
我们定义变量如下图：

在相遇点(meet):

slow指针走了： \(s = l + a \)
fast指针走了： \(2s = l + a + n * r\)

所以 \(l + a = n r = (n - 1) r + r\)

又因为 \( a + x = r\)

所以 \(l = (n - 1) * r + x\)

即从begin到entrance的距离等于从meet点到entrance的距离。

所以，当两者相遇后，一个指针回到起点，另一个不动，两者每次都走一步，等两者相遇，相遇点就是环的入口(entrance)。

单链表的很多问题采用递归很容易求解

leetcode: Reverse Nodes in K-Group

伪代码：

reverseKGroup(ListNode *head, int k){
    先翻转前K个节点。
    然后递归 head->next = reverseKGroup(k+1节点的指针, k);
}

这里再给出一种非递归的写法：

//非递归
//先算出分成几个group
ListNode* reverseKGroup(ListNode* head, int k)
{
    int len =  listLen(head), times = len / k;
    if (head == NULL || times <= 0) {
        return head;
    }
    ListNode *p1, *p2, *p3, *ansHead = head, *tail = head;
    while (times --) {
        p1 = head;
        p2 = p1 -> next;
        p1 -> next = NULL;
        int cnt = 0;
        while (p2 && cnt ++ < k - 1) {
            p3 = p2 -> next;
            p2 -> next = p1;
            p1 = p2;
            p2 = p3;
        }
        //判断是否为第一个group，是则确定整个链表的头部
        if(times == len / k - 1){
            ansHead = p1;
        }
        //连接相邻两个group
        else{
            tail -> next = p1;
            tail = head;
        }
        head = p2;
    }
    while (head) {
        tail -> next = head;
        tail = tail -> next;
        head = head -> next;
    }
    return ansHead;
}

Merge K个有序单链表

方法一：

两两先合并，再一步步合成一个。(类似并归的思想)

注意： List 1与List 2合并，List3与List4合并，最后再把他们的结果合并，这样做一般比按顺序合并要效率高。

方法二：

利用堆来合并。
建立一个大小为K的堆v(最大堆还是最小堆看情况而定)。
make_heap(v.begin(), v.end());

以最小堆为例：
每次选出最小的节点，将其加入新链表的尾部，再将该节点的next节点加入堆中。以此类推直到堆为空。

注意：v是vector容器，v.pop()后，v再 v.push_back(min->next),再push_heap(v.begin(), v.end())，成为新的最小堆。

插入排序

建立哨兵节点是操作方便
ListNode dummy(INT_MIN);

可以做剪枝：cur指针不用每次返回表头，例如对于升序排序的情况，仅当cur->val大于插入节点的val,cur才返回表头。

代码如下：

ListNode* insertionSortList(ListNode* head) {
       ListNode dummy(INT_MIN), *cur, *temp;
       cur = &dummy;
        while(head){
            if(cur->val>head->val) cur = &dummy; // trick, reset cur only when needed 剪枝，cur不用每次都返回哨兵节点
            for (;cur->next && cur->next->val < head->val;) cur=cur->next;
            temp = head->next;
            head->next = cur->next;
            cur->next = head;
            head = temp;
        }
        return dummy.next;
       
        
}

复制带一个随机指针的单链表

leetcode: copy list with random pointer

这题挺有意思，要复制一个带随机指针的单链表，关键就是如何解决这个随机指针的复制。

核心思路：

在原来的链表节点之间插入新的节点即可。

这样随机节点可被巧妙复制！

例如：new2->random = old2->random->next

最后新节点两两相连即可！

代码如下：

RandomListNode *copyRandomList(RandomListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (head == NULL) {  
            return NULL;  
        }  
  
        RandomListNode *node = head;  
        RandomListNode *temp = NULL;  
        //insert new node  
        while (node != NULL) {  
            temp = node->next;  
  
            RandomListNode *newNode = new RandomListNode(node->label);  
            node->next = newNode;  
            newNode->next = temp;  
  
            node = temp;  
        }  
  
        //update new node's random  
        node = head;  
        while (node != NULL) {  
            if (node->random != NULL) {  
                node->next->random = node->random->next;  
            }  
  
            node = node->next->next;  
        }  
  
        RandomListNode *newHead = head->next;  
  
        node = head;  
        RandomListNode *newNode = node->next;  
        while (node != NULL) {  
            node->next = newNode->next;  
            if (newNode->next != NULL) {  
                newNode->next = newNode->next->next;  
            }  
  
            node = node->next;  
            if (node != NULL) {  
                newNode = node->next;  
            }  
        }  
  
        return newHead;  
        
    }