您的位置: 首页  >  文章  >  ch6 - 链表Linked List

ch6 - 链表Linked List

分类: 文章 • 2024-11-09 12:19:07

链表大部分是偏实践的，偏算法的很少。

目录：

  1. 链表基础知识
  2. Reverse Nodes in k-Group (450 in linkcode)
  3. Copy List with Random Pointer (105 in linkcode)
  4. Linked List cycle (102 、103 in linkcode)
  5. Sort List (98 in linkcode)（★★★★★）
  6. merge-two-sorted-lists (165 in linkcode)
  7. insert-into-a-cyclic-sorted-list (599 in linkcode)

1.链表基础知识

1.1 链表指针的赋值，不改变链表的结构和节点本身的值。如两个指针n1，n2，当执行n1 = n2之后，n1本来指向的节点值不变，只是n1现在指向n2了。

1.2 如果要改变链表结构，一定要用 node.属性 = xx

1.3 当需要访问某节点的属性时，无脑判断一个节点或一个节点的next是否为空。

1.4 指针占用的内存空间大小是4byte， 链表节点占用的空间不一定是结构体或类中的所有变量所占内存的和。链表的内存空间在heap中，node1等指针是在stack中。如

class node{
public:
    int val;
    double x;
    node* next;
    node(int v){ val = v; }
};

cout<<sizeof(n)<<endl;
cout<<sizeof(n.val)<<endl;
cout<<sizeof(n.x)<<endl;
cout<<sizeof(n.next)<<endl;

ch6 - 链表Linked List

class node{
public:
    int val;
    node* next;
    node(int v){ val = v; }
};

cout<<sizeof(n)<<endl;    //所占内存空间是8字节。

2.Reverse Nodes in k-Group (450 in linkcode)

2.1.Reverse Linked List（35 in Linkcode）

基本思路：类似交换两个整数的代码。

1->2->3->null 变成：
null<-1<-2<-3

class Solution {
public:
    /*
     * @param head: n
     * @return: The new head of reversed linked list.
     */
    ListNode * reverse(ListNode * head) {
        ListNode * pre = NULL;
        ListNode * cur = head;

        while(cur){
            ListNode * temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }

        return pre;
    }
};

对于single linked list，只有next，所以需要pre和cur等指针

2.2 reverse linked list in k-group （450）

  1. 考虑overview，先考虑整体的框架，再细化里面的每一个细节。

  2. 本题的框架及dummy node的使用：

    A. 定义子函数 reversekNodes（cur，k）：反转当前节点开始的k个节点，返回下一个节点，但是存在一个问题：0->1->2->3->4->null。如果反转1，2，3，除了1，2，3本身发生变化以外，0也会改变，所以如果按照上面的子函数，反转为1->2->3之后，直接开始反转4开始的节点，没有去改变0的next。故：该子函数需要修改，每次翻转k个节点，其实有k+1个节点发生变化。

    B. 链表结构发生变化时，借助dummy node。口->0->1->2->3->4->null。在0前面增加dummy node，不需要关注其value值，只要将其next赋值为head。

  • dummy node什么时候用？ – 当链表结构发生变化时。
  • c++的dummy node如何使用不需要删除？ –
ListNode * dummy = new ListNode(0); //不使用这种方式，这样需要手动释放内存空间。
       ListNode dummy; dummy.next = p; //推荐！！！这样就是一个结构体，代码执行完自动结束

使用dummy node的题目：
http://www.lintcode.com/en/problem/partition-list/
http://www.lintcode.com/en/problem/merge-two-sorted-lists/
http://www.lintcode.com/en/problem/reverse-linked-list-ii/
http://www.lintcode.com/en/problem/swap-two-nodes-in-linked-list/
http://www.lintcode.com/en/problem/reorder-list/
http://www.lintcode.com/en/problem/rotate-list/

3）本题的解题思路
定义子函数 reversekNodes（pre，k） ，每k个进行一次翻转。实现的功能如下：

// head -> n1 -> n2 ... nk -> nk+1
   // =>
   // head -> nk -> nk-1 .. n1 -> nk+1
   // return n1

class Solution {
public:
    /*
     * @param head: a ListNode
     * @param k: An integer
     * @return: a ListNode
     */
    ListNode * reverseKGroup(ListNode * head, int k) {
        // write your code here
        ListNode dummy;
        dummy.next = head;

        head = &dummy;
        while(head){
            head = reverseK(head,k);
            if(!head){
                break;
            }
        }

        return dummy.next;
    }

    ListNode * reverseK(ListNode * head, int k){
        ListNode* nkplus = head;
        for(int i=0;i<=k;++i){
            if(!nkplus){
                return NULL;
            }
            nkplus = nkplus->next;
        }

        ListNode * n1 = head->next; //!!!重要，一定记得存k个节点的第一个，因为翻转之后，需修改该节点的next，使其指向下一个n1
        ListNode * pre = NULL;
        ListNode * cur = head->next;
        while(cur!=nkplus){
            ListNode * temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }

        head->next = pre;
        n1->next = nkplus;

        return n1;
    }
};

3.Copy List with Random Pointer (105 in linkcode)

深度拷贝的题目

思路一：（使用了额外空间）

可以认为每个节点多了一条边，这样相当于图的深度拷贝。
1). find all nodes;
2). copy nodes. hashmap(oldnode->newnode)
3). copy edges (neighbors)

缺点：使用了hashmap的额外空间。（额外空间指的是除了输入输出空间外的空间）

思路二：（使用O（1）的空间）

巧妙借用next。

1->2->3->4->null
=>
1->1’->2->2’->3->3’->4->4’->null

得到原链表中的next： x.next.next

得到节点x对应的新链表中的节点： x.next 等价于 hash[x]

步骤：
1). 增加x’，copy next
2). copy random.
3). split

代码： 劝分不劝和

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */

class Solution {
public:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) {
        // write your code here
        if(!head){
            return NULL;
        }

        copyNext(head);
        copyRandom(head);
        return splitList(head);
    }

    void copyNext(RandomListNode *head){
        while(head){
            RandomListNode * nodecopy = new RandomListNode(head->label);
//            nodecopy->random = head->random;
            nodecopy->next = head->next;
            head->next = nodecopy;
            head = head->next->next;
        }
    }

    void copyRandom(RandomListNode *head){
        while(head){
            if(head->random){
                head->next->random = head->random->next;
            }
            else{
                head->next->random = NULL;  //注意判断head->random是否为空
            }
            head = head->next->next;
        }
    }

    RandomListNode * splitList(RandomListNode *head){
        RandomListNode * newhead = head->next; //注意此处！！！
        while(head){
            RandomListNode * temp = head->next;
            head->next = temp->next;
            if(temp->next){
                temp->next = temp->next->next;
            }
            head = head->next;
        }

        return newhead;
    }
};

4.Linked List cycle (102 、103 in linkcode)

4.1 证明求解方法

1）**以下的证明是fast和slow同时从head开始。**其实就推几个递推公式就好。。首先看图（图引用自CC150）：
ch6 - 链表Linked List

从链表起始处到环入口长度为：a，从环入口到Faster和Slower相遇点长度为：x，整个环长为：c。

明确了以上信息，就可以开始做运算了。。

假设从开始到相遇，Slower走过的路程长为s，由于Faster的步速是Slower的2倍，那么Faster在这段时间走的路程长为2s。

而对于Faster来说，他走的路程还等于之前绕整个环跑的n圈的路程nc，加上最后这一次遇见Slower的路程s。

所以我们有：

               2s = nc + s

对于Slower来说，他走的路程长度s还等于他从链表起始处到相遇点的距离，所以有：

                s = a + x

通过以上两个式子代入化简有：

                a + x = nc

                a = nc - x

                a = (n-1)c + c-x

                a = kc + (c-x)

那么可以看出，c-x，就是从相遇点继续走回到环入口的距离。上面整个式子可以看出，如果此时有个pointer1从起始点出发并且同时还有个pointer2从相遇点出发继续往前走（都只迈一步），那么绕过k圈以后， pointer2会和pointer1在环入口相遇。这样，换入口就找到了。
从链表起始处到环入口长度为：a，从环入口到Faster和Slower相遇点长度为：x，整个环长为：c。

明确了以上信息，就可以开始做运算了。。

假设从开始到相遇，Slower走过的路程长为s，由于Faster的步速是Slower的2倍，那么Faster在这段时间走的路程长为2s。

而对于Faster来说，他走的路程还等于之前绕整个环跑的n圈的路程nc，加上最后这一次遇见Slower的路程s。

所以我们有：

               2s = nc + s

对于Slower来说，他走的路程长度s还等于他从链表起始处到相遇点的距离，所以有：

                s = a + x

通过以上两个式子代入化简有：

                a + x = nc

                a = nc - x

                a = (n-1)c + c-x

                a = kc + (c-x)

那么可以看出，c-x，就是从相遇点继续走回到环入口的距离。上面整个式子可以看出，如果此时有个pointer1从起始点出发并且同时还有个pointer2从相遇点出发继续往前走（都只迈一步），那么绕过k圈以后， pointer2会和pointer1在环入口相遇。这样，换入口就找到了。

2）如果slow从head开始，fast从head->next开始。此时，写代码时的循环条件比较简单，但是上述的递推公式有点点变化。判断是否有环时还是判断fast和slow能否相遇，但是判断环的入口时，则需要修改一下递推公式。

因为开始的时候fast比slow多开始一步，相当于slow多走了一步，所以，最终的递推公式：a = kc + (c-x-1). 所以最终判断的是：slow != fast->next。即fast与slow相遇的地方拒环入口相差：a+1的距离。（slow从head开始）

3)几种特殊情况，注意边际条件

 1->null、    1->2->null、      1->指向自身，有环

4.2 判断链表是否是循环链表 linked-list-cycle （102 in lintcode）

class Solution {
public:
    /*
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    bool hasCycle(ListNode * head) {
        // write your code here
        if(!head || !head->next){  //特殊情况的处理
            return false;
        }

        ListNode * slow = head;
        ListNode * fast = head->next; //slow和fast不要放在同一位置，否则永远进不去循环
        while(slow != fast){
            if(!fast || !fast->next){
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }

        return true;
    }
};

4.3 返回循环链表的入口 linked-list-cycle-ii （103 in lintcode）

class Solution {
public:
/*
* @param head: The first node of linked list.
* @return: The node where the cycle begins. if there is no cycle, return null
*/
ListNode * detectCycle(ListNode * head) {
// write your code here
if(!head || !head->next){
return NULL;
}

    ListNode * slow = head;
    ListNode * fast = head->next;
    while(slow!=fast){
        if(!fast || !fast->next){
            return NULL;
        }
        slow = slow->next;
        fast = fast->next->next;
    }

    slow = head;
    while(slow != fast->next){ //注意此处的判断
        slow = slow->next;
        fast = fast->next;
    }
    return slow; //不能返回fast
}

};

5.Sort List (98 in linkcode)（★★★★★）

5.1 时间复杂度：O(nlog(n))

空间复杂度：O(1) /no extra memory / constant space / O(1) memory complexity

5.2 排序算法 - nlog(n)

quick sort - 期望时间复杂度/平均时间复杂度 nlog(n) - 空间复杂度 O(1)

merge sort - 空间复杂度O(n) 需要有一个新的数组来誊抄

heap(priority queue) sort - 如果在数组上做，并且自己来实现heap的话，空间复杂度O(1) 。在链表上做不到，因为不能进行下标访问。

链表大多数情况下都不需要额外空间。链表上的quick sort和merge sort不需要额外空间。

5.3 quick sort可以实现：

https://www.geeksforgeeks.org/quicksort-on-singly-linked-list/

5.4 merge sort更简单

step 1：findMiddle（快慢指针）；//对数据流问题，不可重新扫，数据实时到来；

step 2：merge two list；

step 3：总框架 { 找中点 -> 左排序（递归） ->右排序（递归） -> 合并 }

5.5 代码

！！！注：
findMiddle函数中，如果fast和slow都从head开始，则 while(fast->next && fast->next->next)
如果slow从head开始，fast从head的下一个开始，则 while(fast && fast->next)

举例：1 -> -1 ->null。mid的位置必须在1，而不是-1，因为right的排序是从mid->next开始的。

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /*
     * @param head: The head of linked list.
     * @return: You should return the head of the sorted linked list, using constant space complexity.
     */
    ListNode * sortList(ListNode * head) {
        // write your code here
        if(!head || !head->next){
            return head;
        }

        ListNode * mid = findMiddle(head);
        ListNode * right = sortList(mid->next);
        mid->next = NULL;
        ListNode * left = sortList(head);

        return merge(left,right);
    }

    ListNode * findMiddle(ListNode * head){
        ListNode * slow = head; //slow和fast可以都从head开始，也可以一前一后
        ListNode * fast = head;

        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode * merge(ListNode * head1, ListNode * head2){
        ListNode dummy(0);
        ListNode * tail = &dummy;

        while(head1 && head2){
            if(head1->val < head2->val){
                tail->next = head1;
                head1 = head1->next;
            }
            else{
                tail->next = head2;
                head2 = head2->next;
            }
            tail = tail->next;
        }

        if(head1){
            tail->next = head1;
        }
        if(head2){
            tail->next = head2;
        }
        return dummy.next;
    }
};

5.6 相关问题

• http://www.lintcode.com/problem/convert-sorted-list-to-balanced-bst/
• http://www.lintcode.com/problem/delete-node-in-the-middle-of-singly-linked-list/
• http://www.lintcode.com/problem/convert-binary-search-tree-to-doubly-linked-list/

6. merge-two-sorted-lists (165 in linkcode)

6.1题目

http://www.lintcode.com/zh-cn/problem/merge-two-sorted-lists/
http://www.jiuzhang.com/solution/merge-two-sorted-lists/
将两个排序链表合并为一个新的排序链表
给出 1->3->8->11->15->null，2->null， 返回 1->2->3->8->11->15->null。

6.2 思路

利用了 sorted List中的merge sort

6.3 代码

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */


class Solution {
public:
    /*
     * @param l1: ListNode l1 is the head of the linked list
     * @param l2: ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    ListNode * mergeTwoLists(ListNode * l1, ListNode * l2) {
        // write your code here
        ListNode dummy(0);
        ListNode * tail = &dummy;

        while(l1 && l2){
            if(l1->val < l2->val){
                tail->next = l1;
                l1 = l1->next;
            }
            else{
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        if(l1){
            tail->next = l1; 
        }
        if(l2){
            tail->next = l2;
        }

        return dummy.next;
    }
};

insert-into-a-cyclic-sorted-list (599 in linkcode)

7.1 题目

http://www.lintcode.com/zh-cn/problem/insert-into-a-cyclic-sorted-list/
http://www.jiuzhang.com/solution/insert-into-a-cyclic-sorted-list/

给一个来自已经排过序的循环链表的节点，写一个函数来将一个值插入到循环链表中，并且保持还是有序循环链表。给出的节点可以是链表中的任意一个单节点。返回插入后的新链表。

给一个链表：3->5->1
插入值 4
返回 5->1->3->4

7.2 思路

1） 注意几个边界条件的判断

2）如果某个节点是需要返回的，则直接用new；如果是类似dummy这样的节点，则用ListNode dummy这样的局部变量。

7.3 代码

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */


class Solution {
public:
    /*
     * @param node: a list node in the list
     * @param x: An integer
     * @return: the inserted new list node
     */
    ListNode * insert(ListNode * node, int x) {
        if(!node){
            node = new ListNode(x);
            node->next = node;
            return node;
        }

        ListNode * cur = node;
        ListNode * pre = NULL;
        do{
            pre = cur;
            cur = cur->next;
            if(x <= cur->val && x>=pre->val){
                break;
            }
            if((pre->val > cur->val) && (x > pre->val || x < cur->val)){
                break;
            }
        }while(cur != node);

        ListNode * newNode = new ListNode(x);
        newNode->next = cur;
        pre->next = newNode;
        return newNode;
    }
};

相关推荐