arttnba3's old blog

- arttnba3的垃圾堆积处 -

0%

【OJ-0x0001-Leetcode】单向链表部分write up by arttnba3

Posted on Edited on In

0x00.绪论

leetcode上面的链表题很有意思，最近做到我废寝忘食都写不出来，所以推荐大家都去写一写（逃

说实话双向链表比单向链表方便的太多了（笑），这点空间复杂度不算什么，建议大家都去写双向链表（不）

不过其实相对于空间复杂度，我更看重时间复杂度，空间复杂度再高一般也不容易爆，然而时间复杂度稍微高一点点往往就容易TLE…（来自OI狗的怨念）

顺便作为大括号换行党吐槽一下Leetcode的不换行机制😡

注：因为题是写不完的，所以这篇文章会不定期的进行更新www

最后一次更新日期为：2020.10.9（终于等来的更新？

Pre:单向链表构造方式

如下，对链表不了解的可以康康我先前写的关于链表的博文：

1
2
3
4
typedef struct ListNode{
	int val;//该节点的值，也可以是其他类型甚至是多个变量
	struct ListNode*next;//指向下一节点的指针
}LN;//通过typedef以达到使用新关键字LN声明ListNode类型结构体变量的目的

（大概长这个样子）
在这里插入图片描述

0x01.难度：简单

0x00.删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 – head = [4,5,1,9]，它可以表示为:

示例 1:

输入: head = [4,5,1,9], node = 5 输出: [4,1,9] 解释: 给定你链表中值为 5
的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 示例 2:

输入: head = [4,5,1,9], node = 1 输出: [4,5,9] 解释: 给定你链表中值为 1
的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明:

链表至少包含两个节点。 链表中所有节点的值都是唯一的。 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-node-in-a-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目当中只给你一个节点，就是要删除的节点，但是在一个单向链表当中，你无法知道这个节点的上一个节点的地址，如何删除？

只要把这个节点变成自己的下一个节点就好了嘛www

注意：在leetcode上面提交时虽然不能使用free()释放被替换节点的内存，但是在实际写删除节点的代码时一定要注意及时释放内存！

注意2：题目虽然保证了输入的绝对合法性，但是在实际写代码时永远不要相信用户的输入！

1
2
3
4
void deleteNode(struct ListNode* node) {
    node->val=node->next->val;
    node->next=node->next->next;    
}

在这里插入图片描述

这么简短的代码还会有那么高的空间复杂度……?

0x01.反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

迭代法

说实话一开始我想的是像数组一样进行交换，但是那样会很麻烦并且时间复杂度会很高，空间复杂度甚至会翻倍

后面看了看大佬的博文，想到可以对这个单向链表进行重构

重新将这个单向链表构造成其反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct ListNode* reverseList(struct ListNode* head)
{
    if(head==NULL||head->next==NULL)
        return head;
	
	struct ListNode* ptr1 = head, *ptr2 = head->next, *temp;
	ptr1->next=NULL;//reset it as the final node
    while(ptr2!=NULL)
    {
    	//注释以第一次构造为例进行说明
        temp=ptr2->next;//储存3号节点
        ptr2->next=ptr1;//2号节点指向1号节点
        ptr1=ptr2;//1号节点变为2号节点（待指向节点）
        ptr2=temp;//2号节点变为3号节点（下一次循环的流程将会使3号指向2号）
    }
	return ptr1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//一年后盲写的版本
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode * temp = NULL, *temp2;
    while(head)
    {
        temp2 = head->next;
        head->next = temp;
        temp = head;
        head = temp2;
    }    
    return temp;
}

在这里插入图片描述

递归法

基本思路其实是和迭代法是一样的，都是对链表进行重构

使用函数递归找到最后一个节点使其成为第一个节点后开始进行重构

缺点就是递归会占用大量的栈空间

代码如下：

1
2
3
4
5
6
7
8
9
10
11
struct ListNode* reverseList(struct ListNode* head)
{
    if(head==NULL||head->next==NULL)
        return head;

    struct ListNode * newhead = reverseList(head->next);//从后往前遍历每个节点
	head->next->next = head;//将当前节点的后一个节点的  next 指向当前结点
	head->next = NULL;//断开当前节点指向后一个节点

	return newhead;
}

在这里插入图片描述

0x02.回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

高空间复杂度的解法一：构建一个反向的单向链表再进行对比（一拍脑门直接想出来的解法XD

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
bool isPalindrome(struct ListNode* head){
    int i=0,j;
    typedef struct sptr {
        struct sptr *last;
        struct ListNode *ptrn;
    }sPtr;
    struct ListNode *ptr=head;
    sPtr *temp,*temp2=NULL;
    while(ptr!=NULL)
    {
        temp=(sPtr*)malloc(sizeof(sPtr));
        temp->last=NULL;
        if(temp2!=NULL)
            temp->last=temp2;
        temp->ptrn=ptr;
        ptr=ptr->next;
        i++;
        if(ptr!=NULL)
            temp2=temp;
    }
    for(j=0;j<i/2;j++)
    {
        if(head->val!=temp->ptrn->val)
            return false;
        head=head->next;
        temp=temp->last;
    }
    return true;
}

很显然，最终的结果惨不忍睹
在这里插入图片描述

进阶解法：快慢指针&链表反转

概念：快慢指针

快慢指针为链表题里用的挺多的一个小技巧

当我们在遍历一个链表的时候，我们可以使用两个指针进行遍历，一个步长为1（为慢指针），一个步长为2（为快指针），这样当快指针走到链表尾的时候，慢指针刚好走到链表的中段

简单的代码实现如下：

1
2
3
4
5
6
7
8
struct ListNode* sptr, *fptr;//slow pointer and fast pointer
int l_list;
for(l_list=0;sptr!=NULL;l_list++)
{
	if(l_list%2)
		sptr=sptr->next;
	fptr=fptr->next;
}

那么我们在判断一个链表是否为回文链表的时候，我们可以选择使用快慢指针对链表进行一次遍历，再将前半部分链表进行反转，之后从头指针开始配合使用慢指针同步对比前后半部分是否相同

反转链表的实现方法在前文已经讲过了，不再做过多解析

最终的代码实现如下：

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
bool isPalindrome(struct ListNode* head)
{
    if(head==NULL||head->next==NULL)
        return true;
    if(head->next->next==NULL)
    {
        if(head->val==head->next->val)
            return true;
        return false;
    }
    struct ListNode * fptr, *sptr, *temp, *temp2, *ptr1, *ptr2;
    int l_list,i;
    fptr=sptr=head;
    for(l_list=0;fptr!=NULL;l_list++)
    {
        if(l_list%2)
            sptr=sptr->next;
        fptr=fptr->next;
    }
    ptr1=head;
    ptr2=head->next;
    ptr1->next=sptr;
    while(ptr2!=sptr)
    {
        temp2=ptr2->next;
        ptr2->next=ptr1;
        ptr1=ptr2;
        ptr2=temp2;
    }
    head=ptr1;
    if(l_list%2)
        sptr=sptr->next;
    l_list/=2;
    for(i=0;i<l_list;i++)
    {
        if(head->val!=sptr->val)
            return false;
        head=head->next;
        sptr=sptr->next;
    }
    return true;
}

在这里插入图片描述

0x03.面试题 02.02. 返回倒数第 k 个节点

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：

给定的 k 保证是有效的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

首先题目保证了给定的k是有效的，那么我们就不需要考虑各种可能出现的奇葩边界情况了，一切数据都是理想数据，真好啊，现实中咋没有这么好的用户呢

那么我们的算法很容易就出来了

解法：双指针

因为当遍历到倒数第k个链表时，该结点的下k个结点必定是NULL，故我们选择使用两个指针来对链表进行同步遍历，第二个指针初始设置为头结点的下k个结点，当第二个指针为NULL时直接返回头结点即可

线性时间复杂度为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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


int kthToLast(struct ListNode* head, int k)
{
    struct ListNode * temp = head;
    for(int i=0;i<k;i++)
        temp = temp->next;
    while(true)
    {
        if(temp == NULL)
            return head->val;
        head = head->next;
        temp = temp->next;
    }
}

image.png

0x04.剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

和0x03基本上思路是一样的，直接双指针一套带走

解法：双指针

因为当遍历到倒数第k个链表时，该结点的下k个结点必定是NULL，故我们选择使用两个指针来对链表进行同步遍历，第二个指针初始设置为头结点的下k个结点，当第二个指针为NULL时直接返回头结点即可

线性时间复杂度为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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
    struct ListNode * temp = head;
    for(int i=0;i<k;i++)
        temp = temp->next;
    while(true)
    {
        if(temp == NULL)
            return head;
        head = head->next;
        temp = temp->next;
    }
}

image.png

0x05.面试题 02.03. 删除中间节点

实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。

示例：

输入：单向链表a->b->c->d->e->f中的节点c
结果：不返回任何数据，但该链表变为a->b->d->e->f

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-middle-node-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题和【简单】0x00是一样的，基本算法是把自身变成自身的下一个结点，这里就不再多讲了

构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void deleteNode(struct ListNode* node) 
{
    node->val = node->next->val;
    node->next = node->next->next;    
}

image.png

0x06.合并两个有序链表

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

遍历l1和l2的每一个结点、比较大小并进行重构即可

这里我选择使用额外的两个指针，一个保存头结点，一个作为重构过程中的尾结点

需要注意的是l1和l2有可能为NULL以及不要忘了把l1或l2的剩余部分进行拼接

C语言版：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
    if(!l1)
        return l2;
    if(!l2)
        return l1;
    struct ListNode * head, *temp;
    if(l1->val>l2->val)
    {
        head = l2;
        l2 = l2->next;
    }
    else
    {
        head = l1;
        l1 = l1->next;
    }
    temp = head;
    while(l1&&l2)
    {
        if(l1->val>l2->val)
        {
            temp->next = l2;
            temp = l2;
            l2 = l2->next;
        }
        else
        {
            temp->next = l1;
            temp = l1;
            l1 = l1->next;
        }
    }
    if(l1)
        temp->next = l1;
    else
        temp->next = l2;
    return head;
}

活用三目运算符的奇怪写法（指专门写的让人看不懂（雾

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
    if(!l1)
        return l2;
    if(!l2)
        return l1;
    struct ListNode * head, *temp, *temp2;
    head = l1->val < l2->val ? (temp = l1, l1 = l1->next, temp) : (temp = l2, l2 = l2->next, temp);
    temp = head;
    while(l1)
    {
        if(!l2)
        {
            temp->next = l1;
            return head;
        }
        temp = temp->next = l1->val < l2->val ? (temp2 = l1, l1 = l1->next, temp2) : (temp2 = l2, l2 = l2->next, temp2);
    }
    temp->next = l2;
    return head;
}

wX28Sg.png

Python语言版：

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        head = l1 if l1.val < l2.val else l2
        if head == l1:
            l1 = l1.next
        else:
            l2 = l2.next
        temp = head
        while l1 != None:
            if l2 == None:
                temp.next = l1
                return head
            temp.next = l1 if l1.val < l2.val else l2
            temp = temp.next
            if temp == l1:
                l1 = l1.next
            else:
                l2 = l2.next
        temp.next = l2
        return head

wX2iFK.png

0x07.剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

大致思路如下：

  • 如果head是那个要被删除的结点，直接返回head的next结点
  • 使用一个指针ptr遍历链表，如果ptr的next结点是要被删除的结点，直接让ptr的next指向ptr->next->next并返回head即可

构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* deleteNode(struct ListNode* head, int val)
{
    struct ListNode * retn = head;
    if(head->val == val)
        return head->next;
    while(true)
    {
        if(head->next->val == val)
        {
            head->next = head->next->next;
            return retn;
        }
        head = head->next;
    }    
}

image.png

0x08.剑指 Offer 52. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

image.png

在节点 c1 开始相交。

示例 1：

image.png

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

image.png

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

image.png

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
本题与主站 160 题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：双指针

我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。

这样，当它们相遇时，所指向的结点就是第一个公共结点。

构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode * node1 = headA, *node2 = headB;
    while (node1 != node2) 
    {
        node1 = node1 != NULL ? node1->next : headB;
        node2 = node2 != NULL ? node2->next : headA;
    }
    return node1;    
}

image.png

0x09.移除链表元素

删除链表中等于给定值 *val* 的所有节点。

示例:

1
2
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

解法：哨兵结点

分两部分遍历，第一部分遍历把链表从头部开始一直到值非val的所有节点删除，第二部分遍历把后续结点都遍历并删除值为val的结点（将其前一结点的next指针指向该结点的next）

针对第一部分的特殊性，我们使用一个哨兵结点指向头结点，最后返回哨兵结点的next即可

构造代码如下：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode * temp = (struct ListNode*)malloc(sizeof(struct ListNode)), *temp2;
    temp->next = head;
    while(temp->next)
    {
        if(temp->next->val!=val)
            break;
        temp->next = temp->next->next;
    }
    temp2 = temp->next;
    while(temp2)
    {
        while(temp2->next && temp2->next->val == val)
        {
            temp2->next = temp2->next->next;
        }
        temp2 = temp2->next;
    }
    return temp->next;
}

image.png

0x0A.剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：递归

直接递归从最后一个结点开始输出即可

构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* reversePrint(struct ListNode* head, int* returnSize)
{
    if(!head)
    {
        *returnSize = 0;
        return (int*) malloc(sizeof(int)*10000);
    }
    int * temp = reversePrint(head->next, returnSize);
    temp[(*returnSize)++] = head->val;
    return temp;
}

当然，递归以及提前分配数组空间会占用大量空间

wXRs4f.png

优化解法：链表重构

为了避免递归产生的大量栈空间以及提前分配大数组占用的大空间，我们考虑将链表重构为其逆序链表后再从头开始输出即可，重构期间同时也能统计链表长度，避免大量无用空间被占用

当然，因为要遍历两趟链表，所以花费的时间会比初始解法长一些

构造代码如下：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* reversePrint(struct ListNode* head, int* returnSize)
{
    *returnSize = 0;
    if(!head) 
        return (int*) malloc(sizeof(int)*5);
    struct ListNode * temp = NULL, *temp2;
    int n = 0;
    while(head)
    {
        temp2 = head->next;
        head->next = temp;
        temp = head;
        head = temp2;
        n++;
    }
    int * retn = (int*)malloc(sizeof(int)*(n+5));
    while(temp)
    {
        retn[(*returnSize)++] = temp->val;
        temp = temp->next;
    }
    return retn;
}

wXW9PK.png

0x0B.剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

直接把前一题重构链表的代码搬过来即可（其实这题就是【简单】0x01啊

构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode * temp = NULL, *temp2;
    while(head)
    {
        temp2 = head->next;
        head->next = temp;
        temp = head;
        head = temp2;
    }
    return temp;
}

wXWrL9.png

0x0C.链表的中间结点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/middle-of-the-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：快慢指针

初始时将慢指针设为head，快指针设为head->next

慢指针一次走一步， 快指针一次走两步， 快指针为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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head)
{
    if(!head)
        return head;
    struct ListNode * temp = head->next;
    while(temp)
    {
        head = head->next;
        temp = temp->next;
        if(!temp)
            break;
        temp = temp->next;
    }
    return head;
}

wXWTeA.png

0x0D.相交链表

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

image.png

在节点 c1 开始相交。

示例 1：

image.png

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

image.png

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

image.png

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题和【简单】0x08一样，直接套就完事了

解法：双指针

我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。

这样，当它们相遇时，所指向的结点就是第一个公共结点。

构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode *node1 = headA, *node2 = headB;
    while(node1!=node2)
    {
        node1 = !node1 ? headB : node1->next;
        node2 = !node2 ? headA : node2->next;
    }
    return node1;    
}

wXWqFP.png

0x0E.面试题 02.07. 链表相交

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null 。
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

和上一题一模一样，套就完事了，看不懂的回去看上一题我的题解

构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode *node1 = headA, *node2 = headB;
    while(node1!=node2)
    {
        node1 = !node1 ? headB : node1->next;
        node2 = !node2 ? headA : node2->next;
    }    
    return node1;
}

wXWxyQ.png

0x0F.二进制链表转整数

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

示例 1：

输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)
示例 2：

输入：head = [0]
输出：0
示例 3：

输入：head = [1]
输出：1
示例 4：

输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880
示例 5：

输入：head = [0,0]
输出：0

提示：

链表不为空。
链表的结点总数不超过 30。
每个结点的值不是 0 就是 1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-binary-number-in-a-linked-list-to-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

先将链表重构为其反转链表，再用常规的二进制数计算方法即可

构造代码如下：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


int getDecimalValue(struct ListNode* head)
{
    int n = 0, m = 1;
    struct ListNode * temp = NULL, * temp2;
    while(head)
    {
        temp2 = head->next;
        head->next = temp;
        temp = head;
        head = temp2;
    }
    while(temp)
    {
        n += temp->val ? m : 0;
        m*=2;
        temp = temp->next;
    }
    return n;
}

wXfFYV.png

0x10.删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

使用一个指针来遍历链表，若下一个结点为值相同的结点时将该结点扔掉，自身指向下一个结点的下一个结点，否则自身变为下一个结点

构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* deleteDuplicates(struct ListNode* head)
{
    struct ListNode * temp = head;
    while(temp && temp->next)
    {
        if(temp->val == temp->next->val)
            temp->next = temp->next->next;
        else
            temp = temp->next;
    }
    return head;
}

wXfnm9.png

0x11. 环形链表

给定一个链表，判断链表中是否有环。

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

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

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

image.png

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：

image.png

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：

image.png

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：快慢指针

老快慢指针人了，只要链表中存在环那么在遍历过程中步长不一的快慢指针肯定会相遇

构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) 
{
    if(!head)
        return false;
    struct ListNode * ptr1 = head, *ptr2 = head->next;
    while(ptr1 && ptr2)
    {
        if(ptr1 == ptr2)
            return true;
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
        if(!ptr2)
            break;
        ptr2 = ptr2->next;
    }
    return false;
}

image.png

解法二：利用题目数据范围漏洞

题目保证结点数量小于10000，那么只要遍历能循环超过10000次，链表中就必定存在回路

构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) 
{
    int n = 0;
    while(head)
    {
        head = head->next;
        n++;
        if(n > 10000)
            return true;
    }
    return false;
}

wXfJ6e.png

0x12.面试题 02.01. 移除重复节点

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例2:

输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：

链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
进阶：

如果不得使用临时缓冲区，该怎么解决？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：临时数组记录出现元素

由于题目数据范围较小，我们使用一个数组记录某个元素是否出现过即可

线性时间复杂度为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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeDuplicateNodes(struct ListNode* head)
{
    if(!head || !head->next)
        return head;
    int n[20005] = {0};
    struct ListNode * temp = head;
    n[temp->val] = 1;
    while(temp->next)
    {
        if(n[temp->next->val])
            temp->next = temp->next->next;
        else
        {
            temp = temp->next;
            n[temp->val] = 1;
        }
    }
    return head;
}

wXfs1S.png

进阶：两重循环

说是进阶实际上是emmm

用时间换空间，每次遍历前先看该结点是不是在前面的链表中出现过了

构造代码如下：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeDuplicateNodes(struct ListNode* head)
{
    if((!head) || (!head->next))
        return head;
    struct ListNode * temp = head, *temp2;
    while(temp)
    {
        temp2 = temp;
        while(temp2->next)
        {
            if(temp2->next->val == temp->val)
                temp2->next = temp2->next->next;
            else
                temp2 = temp2->next;
        }              
        temp = temp->next;
    }
    return head;
}

[wXfqB9.png

wXfL7R.png

下面的是进阶解法，这样的进阶不要也罢！

0x13.面试题 02.06. 回文链表

编写一个函数，检查输入的链表是否是回文的。

示例 1：

输入： 1->2
输出： false
示例 2：

输入： 1->2->2->1
输出： true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：快慢指针

老快慢指针人le

快指针步长为2，慢指针步长为1，从头开始遍历，当快指针到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
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


bool isPalindrome(struct ListNode* head)
{
    if(!head || !head->next)
        return true;
    struct ListNode * temp = NULL, * temp2, * ptr1 = head, *ptr2 = head;
    while(ptr2)
    {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
        if(!ptr2)
            break;
        ptr2 = ptr2->next;
    }
    while(ptr1)
    {
        temp2 = ptr1->next;
        ptr1->next = temp;
        temp = ptr1;
        ptr1 = temp2;
    }
    while(temp)
    {
        if(temp->val != head->val)
            return false;
        temp = temp->next;
        head = head->next;
    }
    return true;
}

wXfz9K.png

0x14.删除链表M个结点后的N个结点（付费）

买不起leetcode会员，只好根据题目名字猜测内容进行盲打，求富婆包养555

解法：哨兵结点

为了防止从第一个结点就开始删除的情况的发生，故我们新建一个哨兵结点指向链表头

构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode* deleteNodes(ListNode* head, int m, int n) 
{
    struct ListNode * temp = (ListNode*)malloc(sizeof(ListNode));
    temp->next = head;
    head = temp;
    for(int i=0;i<m;i++)
    {
        head = head->next;
    }
    for(int i=0;i<n;i++)
    {
        head->next = head->next->next;
    }
    return temp->next;
}

0xFF.至此，Leetcode单向链表部分【简单】难度的题目，全部结束

下面是难度中等的题目

0x02.难度：中等

0x00.两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

**Talk is cheap. Show me the code.**（其实是因为我懒并且写完也看不懂了 ）

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
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int num,num2,pd=0;//pd为进位标识符
    struct ListNode* temp=(struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val=0;
    temp->next=NULL;
    struct ListNode* temp2=temp;
    while(true)//对两个链表进行遍历，模拟整数加减法
    {
        num=0;
        if(l1==NULL&&l2==NULL)//都遍历完了
        {
            if(pd==1)//进行最后一次计算
                ;
            else
                break;
        }
        else if(l1==NULL)//l1先于l2结束遍历
        {
            num=l2->val;
            l2=l2->next;
        }
        else if(l2==NULL)//l2先于l1结束遍历
        {
            num=l1->val;
            l1=l1->next;
        }
        else//常规运算
        {
            num=l1->val+l2->val;
            l1=l1->next;
            l2=l2->next;
        }
        if(pd)//重置pd
        {
            num+=num2;
            pd=0;
        }
        if(num>9)//进位
        {
            pd=1;
            num2=num/10;
            num%=10;
        }
        temp->val=num;
        if(l1==NULL&&l2==NULL&&pd==0)
            break;
        //分配新的节点进行接续，模拟数组
        struct ListNode* temp3=(struct ListNode*)malloc(sizeof(struct ListNode));
        //节点赋值
        temp3->next=NULL;
        temp->next=temp3;
        temp=temp3;
    }
    return temp2;
}

在这里插入图片描述

0x01.删除链表的倒数第n个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：数组储存结点地址

用一个数组存储每一个节点的地址，我觉得彳亍，并且完成了进阶解法仅扫描一遍的要求

但是有个缺点就是不能够应对任意长度的链表的情况

使用C++中的vector容器或许可以解决数组固定长度的问题？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode * fptr;
struct ListNode *temp[100];
fptr=head;
if(head==NULL)
return head;
int l_list;
for(l_list=0;fptr!=NULL;l_list++)
{
temp[l_list]=fptr;
fptr=fptr->next;
}
if(n==l_list)
return head->next;
temp[l_list-n-1]->next=temp[l_list-n]->next;
return head;
}

在这里插入图片描述

解法二：双指针

思路同【简单】0x03，因为当遍历到倒数第k个链表时，该结点的下k个结点必定是NULL，故我们选择使用两个指针来对链表进行同步遍历，第二个指针初始设置为头结点的下k个结点，当第二个指针的下一个结点为NULL时将第一个指针指向其下一个结点的下一个结点即可

线性时间复杂度为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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    struct ListNode * ptr, *temp;
    temp = ptr = head;
    for(int i=0;i<n;i++)
        temp = temp->next;
    if(temp == NULL)
        return head->next;
    while(true)
    {
        if(temp->next == NULL)
        {
            ptr->next = ptr->next->next;
            return head;
        }
        ptr = ptr->next;
        temp = temp->next;
    }
}

image.png

时隔十个月后回过来看这道题才想到可以用双指针

以及从内存消耗上看得出来这道题在这十个月中已经被无数人轮过le（悲

0x02.反转链表II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一趟扫描进行完成，说实话属实有点麻烦，并且还指定了要反转的位置…

等等，制定了要反转的位置？

那么只要我们在遍历到那个位置的时候进行反转不就好了嘛www

思路：在需要反转的位置重新构建一条新的反转后的链表，构建结束后将其重新嵌入原来的位置

大致是下面的这样一个流程：

原始数据： [1,2,3,4,5] 反转位置：2~4

第一趟循环：1->2->3->4->5 操作：无

第二趟循环：1->3->2->4->5 操作：3->2, 2->4, 1->3

第三趟循环：1->4->3->2->5 操作：4->3, 2->5, 1->4

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
struct ListNode* reverseBetween(struct ListNode* head, int start, int end)
{
    if(start == end)
        return head;
    struct ListNode *returnNode = head, *ergodic = head, *newHead = head, *temp;
    /*
    *	ergodic： 	当前正在遍历的节点
    *	temp： 	 	反转前ergodic的下一节点
    *	newHead： 	反转开始位置的上一节点，若从第一个节点开始反转则恒为第一个节点
    *	returnNode： 最后形成的整个链表的第一个节点
    */
    for(int i=1;i<end;i++)
    {
        if(start <= i)
        {
            temp = ergodic->next;
            ergodic->next = temp->next;
            if(start!=1)//反转从中间开始
            {
                temp->next=newHead->next;
                newHead->next = temp;
            }
            else//从头开始反转，需要时刻变更头节点
            {
                temp->next = newHead;
                newHead = returnNode = temp;
            }
            
        }
        else
        {
            newHead = ergodic;
            ergodic = ergodic->next;
        }
    }
    return returnNode;
}

QQ截图20200423020827.png

0x03.二叉树中的列表

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

示例 1：

输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true
解释：树中蓝色的节点构成了与链表对应的子路径。

示例 2：

输入：head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true

示例 3：

输入：head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：false
解释：二叉树中不存在一一对应链表的路径。

提示：

二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。
链表包含的节点数目在 1 到 100 之间。
二叉树包含的节点数目在 1 到 2500 之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这题咋一看很难的样子，其实仔细一想，这不就是我们常用的递归算法中的二叉树的前序遍历🐎，一股熟悉的感觉扑面而来www

前序遍历：先遍历根节点，再遍历左节点，再遍历又节点

不熟悉递归算法的可以先看看我以前的博文，然后把OpenJudge.1700:八皇后问题给做了，那么这道题的算法你基本上也就该明白了

思路：递归前序遍历二叉树查找对应的"链表"，找到了直接返回True，遍历完整棵树都没找到则返回False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool seek(struct ListNode* head, struct TreeNode* root)//此函数进行对比
{
    if(head == NULL)//链表遍历完了，直接true
        return true;
    if(root == NULL)//链表没完树先到头肯定是false
        return false;
    if(head->val!=root->val)//遍历到一半不一样，肯定是false
        return false;
    return seek(head->next,root->left)||seek(head->next,root->right);
}


bool isSubPath(struct ListNode* head, struct TreeNode* root)//此函数仅用作开始对比的入口
{
    if(root == NULL)
        return false;
    return seek(head,root)||isSubPath(head,root->left)||isSubPath(head,root->right);//根节点||左孩子做根节点||右孩子做根节点
}

QQ截图20200423032409.png

0x04.扁平化多级双向链表

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

示例 1：

输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：

输入的多级列表如下图所示：

image.png

扁平化后的链表如下图：

image.png

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

1—2—NULL
|
3—NULL
示例 3：

输入：head = []
输出：[]

如何表示测试用例中的多级链表？

以 示例 1 为例：

1—2—3—4—5—6–NULL
|
7—8—9—10–NULL
|
11–12–NULL
序列化其中的每一级之后：

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]
为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]
合并所有序列化结果，并去除末尾的 null 。

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

提示：

节点数目不超过 1000
1 <= Node.val <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

没有C语言评测，好气啊（呼呼呼

解法：递归 + 深度优先搜索（DFS）

遍历链表，若有孩子则先扁平化孩子，将该结点下一个结点接到孩子链表尾，该结点接到孩子链表头即可

使用递归可以很方便地实现

构造代码如下：

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution 
{
    public:
        Node* flatten(Node* head) 
        {
            if(!head)
                return head;
            Node * temp = head, *temp2;
            while(temp)
            {
                if(temp->child)
                {
                    temp2 = temp->next;
                    temp->next = flatten(temp->child);
                    temp->next->prev = temp;
                    temp->child = nullptr;
                    while(temp->next)
                        temp = temp->next;
                    temp->next = temp2;
                    if(temp2)
                        temp2->prev = temp;
                }
                else
                    temp = temp->next;
            }
            return head;
        }
};

wX4CGV.png

0x05.旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题让我想起NOIP-2016-DAY1-T1，233333

思路比较简单：我们可以先将该链表结成一个环，然后再从中间断开

观察几个样例我们可以看出断开的位置应当是在第len - (k%len)个结点

构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* rotateRight(struct ListNode* head, int k)
{
    if(!head || !head->next)
        return head;
    struct ListNode * temp=head;
    int len;
    for(len=1;temp->next;temp=temp->next)
        len++;
    temp->next = head;
    k %= len;
    for(temp = head;--len!=k;temp = temp->next);
    head = temp->next;
    temp->next = NULL;
    return head;
}

wX4KG6.png

0x06.剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

image.png

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：

image.png

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：

image.png

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

本题与主站138题相同（指本题不能用C评测但是138能用C评测（x

本题要求的是要进行深层拷贝，也就是说我们需要遍历整个双向链表并逐个拷贝每个节点的值到新的链表结点中

本题的难点主要在random指针上，因为它所指向的是链表中的任一结点，因此random指针的指向就是本题的考点之一

解法：哈希表 + 深度优先搜索（DFS）

考虑到新链表的每一个结点与原链表的每一个结点严格一一对应，故我们可以考虑使用一个哈希表储存对应结点，若该结点已经在表中则直接连接上该结点即可，若不在表中则创建新结点

使用递归进行深度优先搜索可以很好地实现我们的算法

构造代码如下：

STL: unordered_map

unordered_map是C++的STL所提供的一个类似于哈希表的东西，我们用它来实现我们的哈希表

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution 
{
    private:
        unordered_map<Node*,Node*> hash;
    public:
        Node* copyRandomList(Node* head) 
        {
            if(!head)
                return head;
            if(hash.count(head))
                return hash[head];
            
            Node * node = new Node(head->val);
            hash[head] = node;
            node->next = copyRandomList(head->next);
            node->random = copyRandomList(head->random);
            return node;
        }
};

看得出来内存上并不是特别的理想，毕竟类的内存开销是很大的

wxFmDS.png

简单hash：以结点地址作为key

考虑到每个结点的地址的值都是独一无二的，故我们可以使用旧链表结点的地址与新链表结点的地址一一对应构建索引

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution 
{
    private:
        unordered_map<Node*,Node*> hash;
    public:
        Node* copyRandomList(Node* head) 
        {
            if(!head)
                return head;
            if(hash.count(head))
                return hash[head];
            
            Node * node = new Node(head->val);
            hash[head] = node;
            node->next = copyRandomList(head->next);
            node->random = copyRandomList(head->random);
            return node;
        }
};

这样内存的开销也就降下来了

wxkvwD.png

0x07.复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

示例 1：

image.png

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：

image.png

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：

image.png

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

和上一题（【中等0x06】）一模一样，不同的是这题可以用C语言进行评测

构造代码如下：

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
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct TreeNode *next;
 *     struct TreeNode *random;
 * };
 */

struct Node * key[1005]={0}, *value[1005]={0};
int amounts = 0;

struct Node* dsf(struct Node* head)
{
    if(!head)
        return head;
    for(int i=0;i<amounts;i++)
        if(key[i] == head)
            return value[i];
    
    struct Node * node = (struct Node*)malloc(sizeof(struct Node));
    key[amounts] = head;
    value[amounts++] = node;
    node->val = head->val;
    node->next = dsf(head->next);
    node->random = dsf(head->random);
    return node;
}

struct Node* copyRandomList(struct Node* head) 
{
    if(!head)
        return head;
	amounts = 0;

    struct Node * node = (struct Node*)malloc(sizeof(struct Node));
    key[amounts] = head;
    value[amounts++] = node;
    node->val = head->val;
    node->next = dsf(head->next);
    node->random = dsf(head->random);
    return node;
}

wxVKs0.png

0x08.两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

其实就是相当于常规的大数加减：链表版本（老OIer应该都写过无数遍了

解法一：链表逆序

将两个链表先重新构造成其逆序链表，再逐位进行运算即可

构造代码如下：

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
67
68
69
70
71
72
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
    if(!l1)
        return l2;
    if(!l2)
        return l1;
    struct ListNode * temp = NULL, *temp2;
    while(l1)
    {
        temp2 = l1->next;
        l1->next = temp;
        temp = l1;
        l1 = temp2;
    }
    l1 = temp;
    temp = NULL;
    while(l2)
    {
        temp2 = l2->next;
        l2->next = temp;
        temp = l2;
        l2 = temp2;
    }
    l2 = temp;
    int flag = 0;
    struct ListNode * retn = (struct ListNode*)malloc(sizeof(struct ListNode));
    retn->next = NULL;
    while(l1&&l2)
    {
        retn->val = (l1->val + l2->val + flag) % 10;
        flag = (l1->val + l2->val + flag) / 10;
        temp = retn;
        retn = (struct ListNode*)malloc(sizeof(struct ListNode));
        retn->next = temp;
        l1 = l1->next;
        l2 = l2->next;
    }
    while(l1)
    {
        retn->val = (l1->val + flag) % 10;
        flag = (l1->val + flag) / 10;
        temp = retn;
        retn = (struct ListNode*)malloc(sizeof(struct ListNode));
        retn->next = temp;
        l1 = l1->next;
    }
    while(l2)
    {
        retn->val = (l2->val + flag) % 10;
        flag = (l2->val + flag) / 10;
        temp = retn;
        retn = (struct ListNode*)malloc(sizeof(struct ListNode));
        retn->next = temp;
        l2 = l2->next;
    }
    if(flag)
    {
        retn->val = flag;
        return retn;
    }
    return retn->next;

}

wxeKET.png

解法二：栈

进阶解法要求我们不对链表进行重构

当然，既然是逆序运算，我们很容易就能够联想到另外一种受限线性表——栈

我们可以先将两个链表的结点值分别压入两个数组模拟的栈中，这样就变成我们最常见也最喜欢的常规的大数加减了

构造代码如下：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
    if(!l1)
        return l2;
    if(!l2)
        return l1;
    int * n1 = (int*) malloc(sizeof(int) * 99), *n2 = (int*) malloc(sizeof(int) * 99), *temp, temp2;
    int len1 = 0, len2 = 0;
    while(l1)
    {
        n1[len1++] = l1->val;
        l1 = l1->next;
    }
    while(l2)
    {
        n2[len2++] = l2->val;
        l2 = l2->next;
    }
    if(len1<len2)
    {
        temp = n1;
        n1 = n2;
        n2 = temp;
        temp2 = len1;
        len1 = len2;
        len2 = temp2;
    }
    struct ListNode * retn = (struct ListNode*)malloc(sizeof(struct ListNode)), *tmp;
    retn->next = NULL;
    int flag = 0;
    for(len1--,len2--;len2>=0;len1--,len2--)
    {
        retn->val = (n1[len1] + n2[len2] + flag) % 10;
        flag = (n1[len1] + n2[len2] + flag) / 10;
        tmp = retn;
        retn = (struct ListNode*)malloc(sizeof(struct ListNode));
        retn->next = tmp;
    }
    while(len1!=-1)
    {
        retn->val = (n1[len1] + flag) % 10;
        flag = (n1[len1] + flag) / 10;
        tmp = retn;
        retn = (struct ListNode*)malloc(sizeof(struct ListNode));
        retn->next = tmp;
        len1--;
    }
    if(flag)
    {
        retn->val = flag;
        return retn;
    }
    return retn->next;
}

当然，因为需要额外的栈空间，所以空间复杂度上不是很理想（分明是退阶解法

wx8bp6.png

0x09. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

很简单的一个交换结点的题，两两交换即可

构造代码如下：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* swapPairs(struct ListNode* head)
{
    if(!head || !head->next)
        return head;
    struct ListNode * temp, *temp2 = head->next->next, *temp3 = (struct ListNode*) malloc(sizeof(struct ListNode)), *retn = head->next;
    temp3->next = head;
    while(head)
    {
        if(!head->next)
            break;
        temp2 = head->next->next;
        temp = head->next;
        temp3->next = temp;
        temp->next = head;
        head->next = temp2;
        temp3 = head;
        head = temp2;
    }
    return retn;
}

wxsgOA.png

0x0A.重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：快慢指针

两个步长分别为1与2的指针对链表进行遍历，当快指针走到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
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


void reorderList(struct ListNode* head)
{
    if(!head || !head->next)
        return head;
    struct ListNode * fast = head->next->next, * slow = head, *temp = NULL, *temp2;
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
        if(!fast)
            break;
        fast = fast->next;
    }
    temp2 = slow->next;
    slow->next = NULL;
    slow = temp2;
    while(slow)
    {
        temp2 = slow->next;
        slow->next = temp;
        temp = slow;
        slow = temp2;
    }
    slow = temp;
    temp = head;
    while(temp && slow)
    {
        temp2 = temp->next;
        temp->next = slow;
        slow = slow->next;
        temp->next->next = temp2;
        temp = temp2;
    }
    return head;
}

wxy6hT.png

0x03.难度：困难

0x00.合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Leetcode链表题当中唯二的两道难度为困难的题之一，看起来似乎并不难的样子，似乎只需要多次遍历拼接得到一个新的链表就好了

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
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
    if(listsSize == 0)
        return NULL;
    else if(listsSize == 1)
        return lists[0];
    //以上为处理特殊情况
    struct ListNode* head = NULL, *temp;//要返回的新链表的头和遍历变量
    int pd;
    for(int i=0;i<listsSize;)
    {
        int min = 9999999;
        pd = -1;
        for(int j=0;j<listsSize;j++)
        {
            if(lists[j]!=NULL)
            {
                if(lists[j]->val<=min)
                {
                    min=lists[j]->val;
                    pd = j;
                }
            }
        }
        if(pd == -1)
            return head;//都空了的情况
        if(head == NULL)//单独处理头
        {
            head = temp = lists[pd];
            lists[pd] = lists[pd]->next;
        }
        else
        {
            temp->next = lists[pd];
            temp = temp->next;
            lists[pd] = lists[pd]->next;
        }
        if(lists[pd] == NULL)
            i++;
    }
    return head;
}

QQ截图20200423104733.png

毫无疑问，这个拍脑门想出来的算法的时间复杂度极高XD

那么我们应该如何进行优化呢？

咕了，后面再补

0x01.K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

PS：指不能偷懒吗XDDD

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Leetcode链表题当中唯二的两道难度为困难的题之二，确实挺有分量

但是既然我们都做了那么多道链表反转了，那么这题其实我们是可以使用类似的思路的XD

鸽了，下次再写

Welcome to my other publishing channels