【力扣刷题篇】 链表OJ题 -- 双指针的应用， 链表递归方式

21. 合并两个有序链表

1. 题目介绍

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

2. 题目解析

3. 题解

思路一 – 双指针 迭代

• 依旧是老套的双指针的应用
• 两个指针分别指向两个链表， 去进行循环遍历
• 比较两个指针指向的节点的val , 将偏小的那个节点的地址尾插到新链表中

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        ListNode* plist1 = list1;    // 定义双指针， 用于遍历两个链表
        ListNode* plist2 = list2;

        ListNode* phead = NULL;  // 新链表的头指针
        ListNode* tail = NULL;   // 该指针指向新链表的尾节点, 可降低时间复杂度
        while(plist1 && plist2)     // 两个链表在进行插入的时候， 一定会有一个链表率先为空
        {
            if(phead == NULL)   // 第一步， 先为头指针赋值
            {
                if(plist1->val <= plist2->val) 
                {  // 判断两个指针指向的节点val的大小， 来决定插入哪一个节点
                    phead = plist1;
                    tail = plist1;
                    plist1 = plist1->next;
                }
                else  
                {
                    phead = plist2;
                    tail = plist2;
                    plist2 = plist2->next;
                }
            }
            else   // 新链表中已存在节点时， 就需要利用尾指针进行尾插
            {   // 判断两个指针指向的节点val的大小， 来决定插入哪一个节点
                if(plist1->val <= plist2->val)
                {
                    tail->next = plist1;
                    tail = plist1;
                    plist1 = plist1->next;
                }
                else
                {
                    tail->next = plist2;
                    tail = plist2;
                    plist2 = plist2->next;
                }
            }
        }
        if(!plist1)     //  判断那个链表先遍历完， 
        { // 如果链表一， 先被遍历完
            if(!phead) // 如果开始链表一就是空链表
            {
                phead = plist2;
                return phead;
            }
            tail->next = plist2;// 让新链表的尾节点指向链表二
        }
        else
        {   // 如果链表二， 先被遍历完
            if(!phead)  // 如果开始链表一就是空链表
            {
                phead = plist1;
                return phead;
            }
            tail->next = plist1;  // 让新链表的尾节点指向链表一
        }
        return phead;
    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

思路一优化

为思路一设置哨兵头节点， 这样就可以在遍历的时候，省略对于头指针是否为空的判断
哨兵头节点既又头指针的作用， 又使得新链表不为空链表

相对简单， 在此只做思路提示， 代码略过。

思路二 – 递归

链表常用算法， 函数的递归调用

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        if(!list1)
        {
            return list2;
        }
        else if(!list2)
        {
            return list1;
        }
        else if(list1->val <= list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

138 . 随机链表的复制

1. 题目介绍

• 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

• 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

2. 题目解析

也就是对链表进行深度拷贝，

• 对于原链表中的每个节点都为其创建一个副本，
• 且不改变其相对顺序
• 副本中的指针域要指向与原数据域数值相同的新节点
• 也就是说 所创建的副本中 data 不变
• next , random 都变
• 但是副本中每个节点的相对顺序不变

3. 题解

思路一

采取复制拼接链表的方式

• 第一步 ， 遍历原链表， 对于其每个节点进行拷贝 ，然后将其插入到被拷贝的节点之后。 完全遍历整个链表时 第一步完成
• 第二步 , 遍历拼接链表， 对于拷贝的节点， 修改其指针random的指向 ：

    - 假设原链表节点为  prev ， 拷贝链表节点为 next 
    - 那么有  next->random = prev->random->next
1
2

• 第三步 , 在此遍历拼接链表， 对拼接链表进行拆分， 拆成原链表与新拷贝链表
• 第四步， 返回拷贝链表头节点的地址。

class Solution {
public:
    Node* copyRandomList(Node* head) 
    {
        if(!head)
            return NULL;
        Node* phead = head;
        while(phead)
        {
            Node* cur = new Node(phead->val);
            cur->next = phead->next;
            phead->next = cur;
            phead = cur->next;
        }
        phead = head->next;
        Node* cur = phead;
        Node* prev = head;
        while(cur)
        {
            if(!prev->random)
            {
                cur->random = NULL;
                prev = cur->next;
                if(!prev)
                    break;
                cur = prev->next;
            }
            else
            {
                cur->random = prev->random->next;
                prev = cur->next;
                if(!prev)
                    break;
                cur = prev->next;
            }
        }
        cur = phead;
        prev = head;
        while(cur)
        {
            prev->next = cur->next;
            prev = prev->next;
            if(!prev)
            {    
                cur->next = NULL;
                break;
            }
            cur->next = prev->next;
            cur = cur->next;
        }
        return phead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

141. 环形链表

1. 题目介绍

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

2. 题目解析

• 判断链表中是否有环， 有换返回true ,无环返回false
• 不需要返回入环的节点

3. 题解

class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast)        // 如果fast为空就结束while循环
        {
            if(fast->next != NULL)     // fast指向节点的下一个节点不为空， 才可以进行移动
            {
                fast=fast->next->next;
                slow = slow->next;
                if(fast == slow)
                    return true;
            }
            else                 // 如果 fast指向的下一节点为空， 代表当前节点为尾节点
                break;
        }
        return false;        // 从while循环非预期跳出， 代表链表中不存在环 
    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

142 . 环形链表II

1 . 题目介绍

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

2. 题目解析

判断链表中是否带环 ， 带环返回入环的第一个节点的位置， 如果不带环返回空

3. 题解

思路一 – 快慢指针的应用

依旧是老套快慢指针的应用
假设 环外节点数为 a , 指针相遇时， 所走环内节点数为 b, 环内慢指针未遍历节点数为 c
两个指针相遇的那一刻有如下的数学关系:

•  a+n(b+c)+b = 2(a+b)
  1

•  a+(n+1)b+c = 2a+2b
  1

•           a = (n-1)(b+c)+c
  1

也就是说， 环外节点个数 等于 (n-1)倍的环内节点总数 + 环内慢指针未遍历节点数
此时， 在定义一个pos指针， 使其从链表头节点开始移动(同时慢指针也继续移动,二者速度相同)。 当他移动至a个节点后， 恰好与慢指针在入环点相遇

class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast)
        {
            if(fast->next)
            {
                fast = fast->next->next;
                slow = slow->next;
                if(fast == slow)
                {
                    ListNode* pos = head;
                    while(pos != slow)
                    {
                        pos = pos->next;
                        slow = slow->next;
                    }
                    return pos;
                }
            }
            else
            {
                break;
            }
        }
        return NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

160. 相交链表

1. 题目介绍

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构

2. 题目解析

先将两个链表分为等长与不等长两种情况， 然后再去判断是否相交

3. 题解

思路一 – 双指针的应用

运用到了部分数学知识

• 将两个链表中节点的个数分别抽象为 未知量 a 和 b
• 永远有 a+b = b+a;
• 如果两个链表相交， 将链表相交前节点的个数抽象为 a , b 相交后节点个数抽象为 c
• 永远有 a+c+b = b+c+a

思路简介:

• 定义两个双指针， 分别指向链表一和二。 同时更新两个指针。
• 如果链表等长， 指针一和指针二会在链表相交时指向同一节点
• 或者在链表不相交时， 全都指向空
• 如果链表不等长， 指针一和指针二会先有一个指向空(假设为指针一)， 此时让指针一指向指针二指向链表的头节点(同时更新指针二)， 之后继续更新两个指针， 当指针二指向空时 ， 让其指向指针一刚开始指向的链表的头节点(同时更新指针一)。 此时 如果链表不相交， 两个指针随着不断更新， 会出现同时指向空， 如果链表相交， 那么两个指针会同时指向相交节点

于此， 通过循环不断更新两个指针， 循环结束条件便是两个指针相等

• 如果相等时， 指向空， 代表不相交。
• 如果相等时， 指向某个节点， 那么该节点就是相交节点

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        ListNode* plist1 = headA;
        ListNode* plist2 = headB;
        while(plist1 != plist2)
        {
            if(!plist1)
            {
                plist1=headB;
                plist2 = plist2->next;
                continue;
            }
            else if(!plist2)
            {
                plist2 = headA;
                plist1 = plist1->next;
                continue;
            }
            else
            {
                plist1 = plist1->next;
                plist2 = plist2->next;
            }
        }
        if(plist1 == plist2 ==NULL)
        {
            return NULL;
        }
        else
        {
            return plist1;
        }
    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

思路一 – 思路优化

暂无优化

思路

采取双指针
这里是将两个链表看作一个链表 ， 假设我们将这两个链表拼接成了一个链表
两种情况进行拼接，
一 : 链表一在前， 链表二在后， 我们将其称为 链表A
二 ：链表二在前， 链表一在后， 我们将其称为 链表B
指针一遍历链表A。
指针二遍历链表B。

现在我们在脑海中构想一下， 两个链表拼接之后的结果
假设链表一共有a+c = m个节点， 链表二共有b+c = n个节点

1. 如果两个链表不相交， 那么c =0, 则有
   • 链表A (a+b = m+n) :
   • 链表B (b+a = m+n) :
   • 两个指针遍历到链表结尾， 相等的位置则是同时指向空
2. 如果两个链表相交， 那么c 不等于 0 ，则有
   • 链表A (a+c+b+c = m+n) :
   • 链表B (b+c+a+c = m+n) :
   • 此时， a+c+b+c 是不是和链表A中 节点的排列顺序相似？
   • a+c 代表链表一中的m个节点， 然后往后就是 链表二中的b个节点以及后>续的c个节点？
   • b+c+a+c 同理
   • 那么这时候， 两个指针向后遍历， 它们相等的位置一定是 c的位置， 也就是相交节点中的第一个节点。

203. 移除链表元素

1. 题目介绍

• 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

2. 题目解析

• 题目中的头节点并非哨兵头节点， 而是链表中的第一个节点， 它存储信息
• 给的是头节点的地址， 相当于给了一个头指针， 这个指针它指向链表中的第一个节点。
• 因为该函数是值传递， 如果在删除元素的过程中需要更改头指针的指向， 那么我们必须返回形参的值， 也就是返回形参中存储的地址，(最后是用一个结构指针来接受的)
• 要删除的是链表中所有数值域为 val的节点。
• 注意通过指针去访问节点中的结构体成员时， 不要越界。
• 如果指针指向空， 此时就无法访问对应的结构体成员。 坚持访问的话， 就会报错
• 注意空指针的报错情况

3. 题解

思路一 – 双指针迭代 指定删除

采取双指针的形式， 将链表中节点的删除分为需要更改头指针指向与不需要更改头指针指向两种情况
双指针

• 指针cur指向当前节点，
• 指针tail指向cur的前一个节点
• 当cur指向的节点数值域为val时， 将指针tail指向的节点其指针域的指向更改为cur的下一个节点， 然后释放cur指向的节点的内存
• 最后更改cur的指向， 让其指向tail指向的节点的下一个节点。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        ListNode* cur = head;
        ListNode* tail = NULL;
        while(cur != NULL)
        {
            if(cur->val == val && cur == head)
            {
                head = head->next;
                delete cur;
                cur = head;
            }
            else
            {
                if(cur->next->val == val)
                {
                    tail = cur;
                    cur = cur->next;
                    tail->next = cur->next;
                    delete cur;
                    cur = tail->next;
                }
            }
        }
        return head;
    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)     // 同类型算法中运行较快
空间复杂度 : O(1)   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

思路一 代码优化:

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        ListNode* cur = head;
        ListNode* prev = NULL;
        while(cur)
        {
            if(cur->val == val)
            {
                if(cur == head)
                {
                    head = head->next;
                    delete cur;
                    cur = head;
                }
                else
                {
                    prev->next = cur->next;
                    delete cur;
                    cur = prev;
                }
            }
            else
            {
                prev = cur;
                cur = cur->next;
            }
        }
        return head;
    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)   // 同类型算法中运行较慢
空间复杂度 : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

思路二 – 双指针 迭代 删改尾插

• 定义三个指针， 分别为头指针， 尾指针， 当前指针
• 具体是将原链表中所有数值域不为val的节点 ， 依次， 重新链接起来， 最终形成一条不含val值元素的链表
• 这就需要定义一个头指针， 用来指向最终链表的头节点
• 需要一个当前指针， 用于遍历整个链表中所有的节点
• 需要一个尾指针， 用来记录每一个尾节点。
• 因为此种方式， 相当于将值不为vla的节点尾插到新头指针指向的链表中(可以降低时间复杂度)

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        ListNode* tail = NULL;
        ListNode* cur = head;
        ListNode* phead = NULL;
        while(cur)
        {
            if(cur->val != val)
            {
                if(cur == head)
                {
                    phead = head;
                    tail = phead;
                    cur=cur->next;
                }
                else
                {
                    if(phead != NULL)
                    {
                        tail->next = cur;
                        tail = cur;
                        cur = cur->next;
                    }
                    else
                    {
                        phead = cur;
                        tail = cur;
                        cur = cur->next;
                    }
                }
                tail->next = NULL;
            }
            else
            {
                cur=cur->next;
            }
        }
        head = phead;
        return head;
    }
};
作者 : Joekr不是Joker 
时间复杂度 : O(n)
空间复杂度 : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

思路二代码未优化

思路三 – 双指针 优化 添加哨兵头节点 (迭代)

创建一个哨兵头节点， 使得头指针指向该哨兵头节点。

• 此时无论如何删除链表中的任意节点， 都无法删除哨兵头节点，也就无法更改头指针的指向
• 相当于， 为该题的删除节点少了一种情况
• 最终返回新头节点的地址时， 返回的不是哨兵头节点， 而是其指针域指向的节点
• 因此最后需要进行 head = head->next这一步

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        ListNode* Shead = new ListNode;
        Shead->next = head;
        head = Shead;
        ListNode* cur = Shead->next;
        ListNode* prev = Shead;
        while(cur)
        {
            if(cur->val == val)
            {
                prev->next = cur->next;
                delete cur;
                cur = prev->next;
            }
            else 
            {
                prev = cur;
                cur = cur->next;
            }
        }
        head = head->next;
        return head;
    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

思路四 – 递归

• 链表通常以递归的方式去解决实际问题，
• 在这里我们循环遍历列表， 依次删除指定元素， 可以通过定义递归函数来实现。

链表递归思想分析:
在这里， 我们的目的是要从前向后遍历这个链表中的每一个节点， 然后判断是否对其进行删除。 显然最外层是访问链表中的第一个节点， 最内层是访问链表中的最后一个节点。
如果采用递归的思想， 递归函数在调用时， 会不断的向下开辟栈帧， 直到满足某个条件， 最近被开辟的栈帧开始返回结果， 然后执行上一个栈帧，执行后返回结果，就这样依次到第一个开辟的栈帧， 最后返回最终结果
这样来看， 我们就是通过递归不断遍历链表中的节点， 访问的第一个节点一定是链表中的最后一个节点， 也就是最晚开辟的栈帧。
也就是说， 需要通过传递head->next, 去不断递归调用函数

递归建模分析:

•    每次都会对链表中相同顺序处的节点进行比较， val较小的节点其指针域指向val较大的那个节点， 然后让val较大的那个节点与零一链表的下一节点进行比较， 确定那个较小
  1

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        if(head == NULL)    // 当调用到最后一个节点时， 再次调用递归函数， 其指向一定为空， 因此用head == NULL， 来判断递归调用是否不在开辟栈帧
        {
            return head; 
        }
        head->next = removeElements(head->next, val);  // 递归调用函数， 传递参数始终是 head->next, 下一个节点的结果由前一个节点的指针域接受 
        return head->val == val? head->next:head;  // 三目运算符， 当前节点若被删除， 就返回下一个节点的地址， 若不需要被删除就返回当前节点的地址
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

206. 反转链表

1. 题目介绍

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

2. 题目解析

意思是将链表的节点顺序翻转过来，最后一个节点变成第一个节点， 这样依次翻转。

3. 题解

思路一 – 双指针的应用

采取双指针， 两个指针指向的节点一前一后 ， 类似于头插法将节点依次插入到新链表中

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* cur = head;
        ListNode* prev = NULL;
        ListNode* phead = NULL;
        while(cur)
        {
            if(!phead)    // 头插入第一个节点时， 
            {
                phead = cur;
                cur = cur->next;
                phead->next = NULL;
            }
            else     // 头插入后续节点时
            {
                prev = cur;
                cur = cur->next;
                prev->next = phead;
                phead = prev;
            }
        }
        return phead;
    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

思路一 – 代码优化

思路一的代码可以优化， 可优化掉每次循环中的if判断语句
原因是 prev 就是头指针的作用， 既是每次头插时 ，需要向后移动的头节点 ，也是头插完之后的头指针。
优化较简单， 这里不在赘述。

思路二 – 递归函数

该题递归较为复杂
思路如下:

• 假设我们现在有一个链表， 我们希望它的第 n 个节点指向 它的第n-1个节点。
• 也就是(n)->next = (n-1)
• 它就等效于 (n-1)->next->next = (n-1);

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        if(head==NULL || head->next==NULL)
        {
            return head;
        }

        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return newHead;
    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

234. 回文链表

1. 题目介绍

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

2. 题目解析

回文链表中节点的个数一定是偶数

3. 题解

思路一 – 快慢指针

使用快慢指针， 将链表分为两部分， 将第二部分的节点进行反转
之后， 采取双指针分别同时遍历这两部分节点， 查找是否 数据域不同

class Solution {
public:
    bool isPalindrome(ListNode* head)
    {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast)
        {
            if(fast->next != NULL)
            {
                fast = fast->next->next;
                slow = slow->next;
            }
            else
            {
                slow = slow->next;
                break;
            }
        }
        
        ListNode* phead = NULL;
        while(slow)
        {
            if(phead == NULL)
            {
                fast = slow;
                slow = slow->next;
                phead = fast;
                phead->next = NULL;
            }
            else
            {
                fast = slow;
                slow = slow->next;
                fast->next = phead;
                phead = fast;
            }
        }

        slow = head;
        fast = phead;
        while(fast)
        {
            if(fast->val != slow->val)
            {
                return false;
            }
            fast = fast->next;
            slow = slow->next;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

237. 删除链表中的节点

1. 题目介绍

有一个单链表的 head，我们想删除它其中的一个节点 node。
给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。
链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

2. 题目解析

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

• 给定节点的值不应该存在于链表中。
• 链表中的节点数应该减少 1。
• node 前面的所有值顺序相同。
• node 后面的所有值顺序相同。

3. 题解

思路一 – 节点值向前覆盖

将节点node后续节点的data依次向前覆盖。

• 节点node不是尾节点
• 链表中所有节点的值都是唯一的

lass Solution {
public:
    void deleteNode(ListNode* node) 
    {
        ListNode* cur = node;
        while(cur)
        {
            cur->val = cur->next->val;
            if(!cur->next->next)
                cur->next = NULL;
            cur = cur->next;
        }    
    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

876 . 链表的中间结点

1. 题目介绍

给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点

2. 题目解析

链表中的结点个数分为奇数个或是偶数个两种情况
寻找链表中的中间结点， 然后返回这个结点的地址

3. 题解

思路一 – 单指针二次遍历

class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        ListNode* cur = head;
        int count = 0;
        while(cur)
        {
            cur = cur->next;
            ++count;
        }
        cur = head;
        if(count == 1)
        {
            return cur;
        }
        int num=1;
        while(cur)
        {
            cur = cur->next;
            if((++num) == count/2+1)
                break;
        }
        return cur;
    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

思路二 – 双指针之快慢指针

指针一一次走两个， 指针二一次走一个格子 ， 这样当指针一恰好遍历完该链表时， 指针二正好正向中间结点。
需要注意的是 要求双数结点， 返回第二个中间结点。
此时， 我们可以取巧 ， 让双指针均指向第一个结点， 由于链表尾结点的指针域指向为空， 此时我们可以将其看作链表尾部的空节点， 如此奇数个链表依旧是奇数个链表， 偶数个链表依旧是偶数个链表 ，但是在返回时 ，返回的结点恰好就是中间结点。

class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast)
        {
            if(!fast->next)
            {
                return slow;
            }
            else
            {
                fast = fast->next->next;
                slow = slow->next;
            }
        }
        return slow;
    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24