[数据结构与算法]数据结构与算法（Leetcode链表篇）

c数据结构与算法刷题笔记

序言

现在是2022年的夏季，作为即将成为在校本科三年级的我，才意识到我应该好好地写写算法题了。诚然，在前两年的学习过程中，不管是数据库还是计算机网络，亦或者是操作系统，我都学习地相当认真。但即使如此，当你真正潜下心钻研那些问题的时候，我才发现，我只是学了概念而已。Practical的东西实在是没有怎么操作过，即使在学习操作系统的时候，即使是听着南京大学蒋炎岩的OS课，做着OSLab的时候。学校里更多的实训课是使用Java语言来写的，然而我觉得我更应该先把计算机基础学得比较扎实，于是在大一大二的学习中我总是疲于奔命。非常遗憾，由于自己很内向，因此没有什么人告诉我计算机这条路应该怎么走，或者，怎么样的路最适合自己。浑浑噩噩两年，突然幡然醒悟，似乎有点晚，但也不算晚吧。

借着准备考研的契机（其实是两年后，但也不冲突），就刷一下Leetcode和PTA上的算法题，来增强自己的能力。

链表专题

两数相加（2）

给你两个?非空 的链表，表示两个非负的整数。它们每位数字都是按照?逆序?的方式存储的，并且每个节点只能存储?一位?数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lvtDSml2-1659170536006)(image/链表刷题笔记/1658812215257.png)]

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

属于菜鸟的第一直觉

在开始的时候，我的第一直觉是直接把两个数的和直接算出来，然后每次%10，得到数字采用头插法插入链表。

顺着这个思路，我在第一次尝试的时候直接写了这样的代码：

struct ListNode* addTwoNumbers(struct ListNode* l1,struct ListNode*l2){
	//得到两个数的值

	//两个数相加

	//进行%10和插入链表的操作
}

就好像把这个函数功能分成了三个模块。

于是会发现，我要得到每个链表代表的数的值，我就必须知道每个数的权重，我要知道它的权重，我就必须知道链表的结点个数，因此我还需要求length。

//length其实各种链表的题都会涉及
int getLength(struct ListNode *head){
	int length = 0;
	while(head){
	++length;
	head = head->next;
	}
	return length;
}

于是就可以通过循环，得到每个链表代表的数的值

int sum1 = 0;
for(;length>0 && head;length --){
	sum1 += head->val * pow(10,length-1);
	if(head->next != NULL)head = head->next;
}

接着就能知道这个数具体的值。

然后就是经典的知道一个整数判断它的位数：

如果想要判断一个整数的位数，那么就必须要用循环语句一位一位的计算，当x大于0时，进入循环。x除以10取整，如果x取整之后大于0，说明x不止一位，那么继续进行循环，循环一次i+1，直到x=0时，说明已经除到最高位了，那么我们就可以退出循环，输出次数i了。

int i = 0;
while(x > 0){
	i++;
	x /= 10;
}

然后就可以根据位数和值用循环依次插入链表。

虽然实际操作起来这种方法也不难，但是不难发现，太复杂了。于是看了下面的官方题解。

官方题解（答案之一）

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *head = NULL, *tail = NULL;
    int carry = 0;
    while (l1 || l2) {
        int n1 = l1 ? l1->val : 0;
        int n2 = l2 ? l2->val : 0;
        int sum = n1 + n2 + carry;
        if (!head) {
            head = tail = malloc(sizeof(struct ListNode));
            tail->val = sum % 10;
            tail->next = NULL;
        } else {
            tail->next = malloc(sizeof(struct ListNode));
            tail->next->val = sum % 10;
            tail = tail->next;
            tail->next = NULL;
        }
        carry = sum / 10;
        if (l1) {
            l1 = l1->next;
        }
        if (l2) {
            l2 = l2->next;
        }
    }
    if (carry > 0) {
        tail->next = malloc(sizeof(struct ListNode));
        tail->next->val = carry;
        tail->next->next = NULL;
    }
    return head;
}

官方题解看起来就清爽得多了。

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为n1,n2，进位值为 carry，则它们的和为 n1+n2+carry；其中，答案链表处相应位置的数字为（n1+n2+carry）mod 10 ，而新的进位值也很好算

如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。

此外，如果链表遍历结束后，有carry>0，还需要在答案链表的后面附加一个节点，节点的值为carry。

说白了就是小学二年级数学里的进位运算。第一位管第一位加，有进位给后面再运算，一个链表加完了就默认另一个值加的0；

int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;

这段就是防止一个链表加完的情况

if (!head) {
            head = tail = malloc(sizeof(struct ListNode));
            tail->val = sum % 10;
            tail->next = NULL;
        } else {
            tail->next = malloc(sizeof(struct ListNode));
            tail->next->val = sum % 10;
            tail = tail->next;
            tail->next = NULL;
        }

这段的意思是，如果还没有头结点的话，新建一个头结点，头结点的值为n1+n2+carry的个位数部分

已经有头结点的时候，为当前尾结点分配一个后继节点，并赋值，同时尾结点指向新的尾结点。

 carry = sum / 10;

然后得到进位数的值，使其在下一次循环中加入运算。

if (carry > 0) {
        tail->next = malloc(sizeof(struct ListNode));
        tail->next->val = carry;
        tail->next->next = NULL;
    }

当两个链表都读完的时候，有可能还存在一个进位，我们再把这个进位处理掉即可。

删除链表倒数第N个结点（19）

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eM6XDwxW-1659170536007)(image/链表刷题笔记/1658814935055.png)]

示例 1：

输入：head = [1,2,3,4,5], n = 2

输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1

输出：[]

示例 3：

输入：head = [1,2], n = 1

输出：[1]

提示：

链表中结点的数目为 sz

1 <= sz <= 30

0 <= Node.val <= 100

1 <= n <= sz

属于菜鸟的第一直觉

看到这个题，心里就一个想法：区区一个删除结点的问题而已。所以只要找到这个结点前驱节点就好说了，换言之，只需要知道这是第几个结点就行了。

于是通过遍历可以知道这个链表的节点个数，通过count - n + 1可以知道这个删除结点是第几个数。但一个程序应该要具备健壮性。

灵魂问题：

1. 不带头结点的链表，你是否需要考虑过如何处理头结点？
2. 如何对链表的最后一个结点进行处理?

没有考虑这两个问题，很容易出现测试用例通不过的情况。

很不幸得是，愚蠢的我通过测试用例的报错信息，归纳出了限制条件，然后才通过了这个程序。这也就是为什么abs-2>0 为什么有这些if语句的原因。

当然，你可以从归纳出的条件得到很多有用的信息。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    int abs = 0 ; //Define absolute position
    int count = 0;//Define counter
    struct ListNode *p = malloc(sizeof(struct ListNode));
    //Define temp as p
    p = head;
    while(p){
        count ++;//To get the result of nums of elemtype
        p = p->next;
    }
    abs = count + 1 - n;//test 82 1,2,3,4,5,6,7,8,9,10 n=7  abs=4
    p = head;
  
    while(abs - 2> 0){
        p = p->next;
        abs -- ;
    }
    if(count == 1)return NULL;
    if(n == 1){
        p = head;
        while(count != 2){
            p = p->next;
            count -- ;
        }
        p->next = NULL;
    }else if (n == count){
        head = head -> next;
    }
    else p->next = p->next->next;
    return head; 
}

当然你也看的出来，这样的程序看起来就很复杂。

这是它的执行效率：

执行用时：4 ms, 在所有 C 提交中击败了51.18%的用户

内存消耗：5.5 MB, 在所有 C 提交中击败了98.92%的用户

官方题解（答案之一）

int getLength(struct ListNode* head) {
    int length = 0;
    while (head) {
        ++length;
        head = head->next;
    }
    return length;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0, dummy->next = head;
    int length = getLength(head);
    struct ListNode* cur = dummy;
    for (int i = 1; i < length - n + 1; ++i) {
        cur = cur->next;
    }
    cur->next = cur->next->next;
    struct ListNode* ans = dummy->next;
    free(dummy);
    return ans;
}

官方题解告诉我们了一个非常有用和重要的技巧——哑结点（dummy node）；

如菜鸟的第一直觉中提到的灵魂问题，对于没有头结点的链表，我们需要对第一个结点进行特殊处理。

而哑结点恰恰能规避这个问题，不管是从逻辑上还是物理上都使得这个问题大大地简化。

合并两个有序链表（21）

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2vVtHbbf-1659170536008)(image/链表刷题笔记/1658816032404.png)]

属于菜鸟的第一直觉

这是一道简单题，所以也费不了多少力我就想出了一种解法；

和两数相加（2）一样，对于每个链表的头部开始，不断比较大小，再插入链表即可。问题也就是其中一个链表走完了之后怎么处理得问题。

实际上这还是和两数相加（2）类似，只不过一个赋值0，一个赋值一个很大的数。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    int n;

    struct ListNode* head = malloc(sizeof(struct ListNode));
    struct ListNode *s,*r = head;//r is pointer of tail
    while(list1 || list2){
        int n1 = list1 ? list1->val : 9999999;
        int n2 = list2 ? list2->val : 9999999;

        n = n1 < n2 ? n1 : n2;//取两个表头最小值
        if(n1 < n2 && list1)list1 = list1->next;
        if(n2 <= n1 && list2)list2 = list2->next;
  
        s  = malloc(sizeof(struct ListNode));
        s->val = n;
        // s->next = NULL;
        r->next = s;
        r = s;
    }
    r->next = NULL;
    return head->next;
}

两两交换链表中的结点（24）

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O8DuIQcG-1659170536008)(image/链表刷题笔记/1658816705232.png)]

官方题解（答案之一）

struct ListNode* swapPairs(struct ListNode* head){
    struct ListNode *dummyhead = malloc(sizeof(struct ListNode));
    dummyhead->next = head;
    struct ListNode *current = dummyhead;
    while(current->next != NULL && current->next->next != NULL){
        struct ListNode *node1 = current->next;//the node after current pointer
        struct ListNode *node2 = current->next->next;
        current->next = node2;
        node1->next = node2->next;
        node2->next = node1;
        current = node1;
    }
    return dummyhead->next;
}

可以通过迭代的方式实现两两交换链表中的节点。

然后设置一个哑结点就不用特殊处理头结点了！真的很Nice.

其实这些程序只要注意一下判断条件和非法指针访问的问题，程序本身不难想。

旋转链表（61）

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VB9s50FT-1659170536009)(image/链表刷题笔记/1659147227748.png)]

属于菜鸟的第一直觉

看到这个题，我的第一直觉是让尾结点的前驱节点指向空，让尾结点的后继节点指向前驱结点

int getLength(struct ListNode* head){
    int length = 0;
    while(head){
        ++length;
        head = head->next;
    }
    return length;
}

struct ListNode* rotateRight(struct ListNode* head, int k){
  
    int length = getLength(head);//O(N)
    if(length == 1 || length == 0)return head;
    else {while(k){ //O(N^2)
        --k;
    /*尾指针->next = 头指针*/
    struct ListNode* temp = head;
    struct ListNode* ans = head;
    while(temp->next){
        temp = temp->next;
    }
  
    int j = length;
    while(j>2){
        --j;
        head = head->next;
    }
    head->next = NULL;
    temp->next =ans;
    head = temp;
    }
    return head;}
}

然后对于只有一个元素和空链表做单独处理即可

然后在leetcode里能通过大部分的测试用例，但是并不能完全通过，会遇到超时的问题。

然后我动了动我的猪脑子，换了一种算法：

int getLength(struct ListNode* head){
    int length = 0;
    while(head){
        ++length;
        head = head->next;
    }
    return length;
}

struct ListNode* rotateRight(struct ListNode* head, int k){
  
    int length = getLength(head);//O(N)
    if(length == 1 || length == 0)return head;
    else{
        while(k){
            --k;
        struct ListNode *tail  = head;
        while(tail->next){
            tail = tail->next;
        }
        struct ListNode *thead = head;
        int i = length;
        while(i>1){
            --i;
            head = head->next;
            thead->next = NULL;
            tail->next = thead;
            tail = thead;
            thead = head;
        }
        }
        return head;
    }
  
}

好吧，还是超时。但这一段代码比上一段代码至少看起来就简单很多了。

但我思考了一下，链表遍历肯定需要O(n)时间复杂度,循环K次也需要O(k)的时间复杂度。遍历的时间降不下来，那就只能看看k这个变量，实际上当次数上去之后，我们没有必要循环这么多次，因为循环链表的长度的整数倍和不循环是一样的。因此我们可以把k降下来。所以只需要让count = k % length，循环次数就小于链表长度了。

int getLength(struct ListNode* head){
    int length = 0;
    while(head){
        ++length;
        head = head->next;
    }
    return length;
}

struct ListNode* rotateRight(struct ListNode* head, int k){
  
    int length = getLength(head);//O(N)
    int count;
    if(length != 0)count = k % length;
    if(length == 1 || length == 0)return head;
    else{
        while(count){
            --count;
        struct ListNode *tail  = head;
        while(tail->next){
            tail = tail->next;
        }
        struct ListNode *thead = head;
        int i = length;
        while(i>1){
            --i;
            head = head->next;
            thead->next = NULL;
            tail->next = thead;
            tail = thead;
            thead = head;
        }
        }
        return head;
    }
  
}

不过官方题解总能给到我启发：

官方题解（答案之一）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9wMZ3vQM-1659170536009)(image/链表刷题笔记/1659148962321.png)]

struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (k == 0 || head == NULL || head->next == NULL) {
        return head;
    }
    int n = 1;
    struct ListNode* iter = head;
    while (iter->next != NULL) {
        iter = iter->next;
        n++;
    }
    int add = n - k % n;
    if (add == n) {
        return head;
    }
    iter->next = head;
    while (add--) {
        iter = iter->next;
    }
    struct ListNode* ret = iter->next;
    iter->next = NULL;
    return ret;
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/rotate-list/solution/xuan-zhuan-lian-biao-by-leetcode-solutio-woq1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

删除排序链表中的重复元素2（82）

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yQx7RrAg-1659170536009)(image/链表刷题笔记/1659169512495.png)]

官方题解

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0gKVMVpM-1659170536010)(image/链表刷题笔记/1659169605220.png)]

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (!head) {
        return head;
    }

    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->next = head;

    struct ListNode* cur = dummy;
    while (cur->next && cur->next->next) {
        if (cur->next->val == cur->next->next->val) {
            int x = cur->next->val;
            while (cur->next && cur->next->val == x) {
                cur->next = cur->next->next;
            }
        } else {
            cur = cur->next;
        }
    }

    return dummy->next;
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/solution/shan-chu-pai-xu-lian-biao-zhong-de-zhong-oayn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。