数据结构——单链表典型例题解析_单链表编程题

1.移除链表元素

1.1 题目

203. 移除链表元素 - 力扣（LeetCode）

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

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

1.2 解答

思路1：遍历链表，在原链表执行删除指针的操作

思路2：不修改原链表，创建新链表，将原链表中不为val的值保存到新链表

思路2的代码实现如下：

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    //创建新链表
    ListNode* newhead, * newtail;
    newhead = newtail = NULL;
    //遍历原链表
    ListNode* pcur = head;
    while(pcur)
    {
        //找值不为val的结点
        if(pcur->val != val)
        {
            //进行尾插操作
            if(newhead == NULL)
            {
                //此时既为尾结点，也为新结点
                newhead = newtail = pcur;
            }
            else
            {
                //链表不为空
                newtail->next = pcur;
                newtail = newtail->next;
            }
        }
        pcur = pcur->next;
    }
    if(newtail)
        newtail->next = NULL;
    return newhead;
}

1.3 注意事项

在代码中我们最容易忽视的就是最后一段代码

if(newtail)
    newtail->next = NULL;

如果不置空，那么如果最后一个链表中的数据等于val，则在最终的结果中也会出现最后一个链表中的数据，这是因为在原来的链表中连接的关系没有转变，因此，这一段代码是必要的。

2.反转链表

2.1 题目 

206. 反转链表 - 力扣（LeetCode）

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

2.2 解答

思路1：进行头插操作

思路2：

思路2的代码实现如下：

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL)
        return head;
    ListNode* n1,* n2, * n3;
    n1 = NULL, n2 = head, n3 = head->next;
    while(n2)//由图可以看出，当n2为空时，循环结束
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)//n3会提前为空
        {
            n3 = n3->next;
        }
    }
    //此时n1就为头结点
    return n1;
}

2.3 注意事项

在上述代码中我们最重要的是找到三个变量的转换关系，其次，还要注意链表为空的情况（如示例3）。

3.链表的中间节点 

3.1 题目 

876. 链表的中间结点 - 力扣（LeetCode）

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

3.2 解答 

思路：快慢指针的典型运用

快慢指针：慢指针每次移动一个结点，快指针每次移动两个结点，当快指针到达NULL时，慢指针搞好就在中间结点的位置，即2/n的位置。

代码实现如下：

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next)
    //偶数个结点的判断条件是fast == NULL;
    //奇数个结点的判断条件是fast->next == NULL;
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

3.3 注意事项

1.我们应该分不同的情况：奇数个结点和偶数个结点

2.fast && fast->next 两个判断条件位置不能改变，因为如果是 fast->next && fast 那么当fast->next为空时，直接短路，那么就永远判断不了fast 为空的情况。 

4.合并两个有序链表

4.1 题目

21. 合并两个有序链表 - 力扣（LeetCode）

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

4.2 解答 

思路:遍历原链表，比较大小，谁小，尾插到新链表中

代码实现如下：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 判断为空的情况
    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;
    // 创建新链表
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;
    // 创建两个指针分别指向两个链表的头结点
    // 目的是为了保留原来两个链表的头结点
    ListNode* l1 = list1;
    ListNode* l2 = list2;
 
    while (l1 && l2)
    // 只要有一个为空，就跳出循环
    {
        // 比较两个大小
        if (l1->val < l2->val) {
            // l1尾插到新链表中
            if (newhead == NULL) {
                newhead = newtail = l1;
            } else {
                newtail->next = l1;
                newtail = newtail->next;
            }
            l1 = l1->next;
        } else {
            // l2尾插到新链表中
            if (newhead == NULL) {
                newhead = newtail = l2;
            } else {
                newtail->next = l2;
                newtail = newtail->next;
            }
            l2 = l2->next;
        }
    }
    // 有两种情况，l1为空，l2为空
    if (l1) {
        newtail->next = l1;
    }
    if (l2) {
        newtail->next = l2;
    }
    return newhead;
}

 虽然上述代码在提交的时候是正确的，但是，我们会发现中间会有相似的部分，那么有没有什么办法可以改进呢？

我们在上述代码中多次要判断指针为空的情况，那么我们可不可以有什么办法来解决呢？

在定义新链表时，我们可以为新链表的头结点申请空间，这样就减少了对于链表为空的情况的判断。

代码改进如下：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 判断为空的情况
    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;
    // 创建新链表
    ListNode* newhead;
    ListNode* newtail;
    newhead = newtail =(ListNode*)malloc(sizeof(ListNode));
    
    // 创建两个指针分别指向两个链表的头结点
    // 目的是为了保留原来两个链表的头结点
    ListNode* l1 = list1;
    ListNode* l2 = list2;
 
    while (l1 && l2)
    // 只要有一个为空，就跳出循环
    {
        // 比较两个大小
        if (l1->val < l2->val) {
            // l1尾插到新链表中
                newtail->next = l1;
                newtail = newtail->next;
                l1 = l1->next;
        } else {
            // l2尾插到新链表中
                newtail->next = l2;
                newtail = newtail->next;
                l2 = l2->next;
        }
    }
    // 有两种情况，l1为空，l2为空
    if (l1) {
        newtail->next = l1;
    }
    if (l2) {
        newtail->next = l2;
    }
    ListNode* ret = newhead->next;
    free(newhead);
    newhead = NULL;
    return ret;
}

4.3 注意事项

1.根据示例，我们应该首先判断两个链表为空的情况；

2. 当为改进代码时，我们还要注意在最后要释放我们所申请的内存，使得代码更加规范。

5.链表分割

5.1 题目 

链表分割_牛客题霸_牛客网 (nowcoder.com)

描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

5.2 解答 

 要注意题目中所说的结点的相对位置不能发生改变

 思路：创建两个链表，一个为小链表，一个为大链表，然后遍历链表，将小于规定值的结点尾插到小链表，其余的尾插到大链表。

代码实现如下：

#include <cstddef>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        
        //创建两个非空链表，小链表和大链表
        ListNode* lesshead, *lesstail;
        lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));
 
        ListNode* greaterhead, * greatertail;
        greaterhead = greatertail = (ListNode*)malloc(sizeof(ListNode));
 
        //遍历链表，分别尾插到大小链表中
        ListNode* pcur = pHead;
        while(pcur)
        {
            if(pcur->val < x)
            {
                //尾插到小链表中
                lesstail->next = pcur;
                lesstail = lesstail->next;
            }
            else 
            {
                //尾插到大链表中
                greatertail->next = pcur;
                greatertail = greatertail->next;
            }
            pcur = pcur->next;
        }
        //大小链表首尾相连
        greatertail->next = NULL;
        lesstail->next = greaterhead->next;
        ListNode* ret = lesshead->next;
        //释放
        free(lesshead);
        free(greaterhead);
        lesshead = NULL;
        greaterhead = NULL;
        //返回值
        return ret;
    }
};

5.3 注意事项 

1.要记得在大链表中最后一个结点的指向为NULL，否则就会实现环，形成死循环；

2.要运用中间变量ret；

3.记得在最后要释放申请的空间。 

6.链表的回文结构 

6.1 题目 

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

6.2 解答 

回文：数字呈现轴对称的情况为回文结构，例如上述所呈现的1->2->2->1的结构。

思路1：将链表逆置，与原来的链表进行比较。

思路2：创建一个数组，在数组中进行比较判断。

思路2的代码实现如下：

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
 
        //创建数组
        int arr[900] = {0};
        ListNode* pcur = A;
        int  i = 0;
        //遍历链表
        while(pcur)
        {
            arr[i++] = pcur->val;
            pcur = pcur->next;
        }
        //i就是结点的个数
        //找中间结点，判断是否为回文数字
        int left = 0;
        int right = i - 1;
        while(left < right)
        {
            if(arr[left] != arr[right])
            {
                //不是回文结构
                return false;
            }
            left++;
            right--;
        }
        //是回文结构
        return true;
    }
};

思路3：在链表上进行遍历，我们用到反转链表。

          1.找链表的中间结点（用快慢指针）；

          2.将中间结点之后的链表进行反转。

思路3的代码实现如下：

class PalindromeList {
public:
    ListNode* findMidNode(ListNode* phead)
    {
        ListNode* slow = phead;
        ListNode* fast = phead;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* reverseList(ListNode* phead)
    {
        ListNode* n1, * n2, * n3;
        n1 = NULL, n2 = phead, n3 = phead->next;
        while(n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n3)
                n3 = n3->next;
        }
        return n1;
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
 
        //1.找中间结点
        ListNode* mid = findMidNode(A);
        //2.根据中间结点反转后面的链表
        ListNode* right = reverseList(mid);
        //3.根据原链表和反转后的链表比较结点的值
        ListNode* left = A;
 
        while(right)
        {
            if(left->val != right->val)
            {
                return false;
            }
            left = left->next;
            right = right->next;
        }
        return true;
    }
};

6.3 注意事项

1.在思路2中，我们其实又开辟了新的空间，题目中有对链表结点个数的限制，可以使用这样的方法；但是，如果没有对链表结点个数的限制，这种思路是行不通的。 

2.思路3中主要是运用了快慢指针找中间结点，然后运用了反转链表，使得这个题更加简单。

7.相交链表 

7.1 题目 

160. 相交链表 - 力扣（LeetCode）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
• listA - 第一个链表
• listB - 第二个链表
• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

 

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

 

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,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 。

 

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB] 

 

 7.2 解答

相交：两个链表从头开始遍历，尾结点 一定是同一个结点。在整个链表中不存在环。

思路：考虑链表的结点个数是否相同，分别遍历，然后比较值。

代码实现如下：

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode* l1 = headA;
    ListNode* l2 = headB;
    int sizeA = 0, sizeB = 0;
    //1.找两个链表的差值
    while(l1)
    {
        sizeA++;
        l1 = l1->next;
    }
    while(l2)
    {
        sizeB++;
        l2 = l2->next;
    }
    int gap = abs(sizeA - sizeB);
    //2.长链表走差值步
    ListNode* longList = headA;
    ListNode* shortList = headB;
    if(sizeA < sizeB)
    {
        longList = headB;
        shortList = headA;
    }
    while(gap--)
    {
        longList = longList->next;
    }
    //此时longList和shortList指针在同一起跑线上
    while(longList && shortList)
    {
        if(longList == shortList)
        {
            return longList;
        }
        //不相等，继续往后走
        longList = longList->next;
        shortList = shortList->next;
    }
    //链表不相交
    return NULL;
}

7.3 注意事项

本题思路比较简单，只要把步骤弄清楚后，就可以实现。 

8.环形链表 

8.1 环形链表（1）

8.1.1 题目

141. 环形链表 - 力扣（LeetCode）

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

8.1.2 解答 

 带环：链表尾结点next指针不为空。

思路：运用快慢指针，若两个指针相遇，则链表带环。

代码实现如下：

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    //快慢指针的定义
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            return true;
        }
    }
    //两个指针没有相遇
    return false;
}

分析如下：

那么，现在有一个问题：如果快指针每次所走的不是2步，而是3步，4步...还会相遇吗？

分析如下： 

综上所述，无论是哪一种情况，都可以相遇！ 

8.1.3 注意事项

在写代码时，我们也可能会用到数学知识，来证明代码的正确性。

8.2 环形链表（2） 

8.2.1 题目 

142. 环形链表 II - 力扣（LeetCode）

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

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

不允许修改 链表。

示例 1：

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

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

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

提示：

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

8.2.2 解答  

 思路：让一个指针从链表起始位置开始遍历链表，同时，让一个指针从判环时相遇点的位置开始绕环运行，两个指针均走一步，最终在入口点汇合。

代码实现如下：

typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    //找环的相遇点
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast &&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            //相遇,链表带环
            ListNode* pcur = head;
            while(pcur != slow)
            {
                pcur = pcur->next;
                slow = slow->next;
            }
            return pcur;
        }
    }
    return NULL;
}

分析：为什么可以用这种方法？

 

9.随机链表的复制 

9.1 题目 

138. 随机链表的复制 - 力扣（LeetCode） 

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

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

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

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

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

你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 0 <= n <= 1000
• -104 <= Node.val <= 104
• Node.random 为 null 或指向链表中的节点。

9.2 解答 

与其他的链表不同的是，这里多了一个random指针 ，且random指针指向的对象不确定。

思路：

 

 

代码实现如下：

typedef struct Node Node;
Node* BuyNode(int x)
{
    Node* newnode = (Node*)malloc(sizeof(Node));
    newnode->val = x;
    newnode->next = newnode->random = NULL;
    return newnode;
}
void AddNode(Node* phead)
{
    Node* pcur = phead;
    while(pcur)
    {
        Node* Next = pcur->next;
        //创建新结点
        Node* newnode = BuyNode(pcur->val);
        //尾插到pcur的后面
        pcur->next = newnode;
        newnode->next = Next;
 
        pcur = Next;
    }
}
struct Node* copyRandomList(struct Node* head) {
    if(head == NULL)
        return head;
	//原链表上复制结点
    AddNode(head);
    //置random
    Node* pcur = head;
    while(pcur)
    {
        Node* copy = pcur->next;
        if(pcur->random != NULL)//默认值就为NULL
        {
            copy->random = pcur->random->next;
        }
        pcur = copy->next;
    }
    //断开链表
    pcur = head;
    Node* newhead, * newtail;
    newhead = newtail = pcur->next;
    while(pcur->next->next)
    {
        pcur = pcur->next->next;
        newtail->next = pcur->next;
        newtail = newtail->next;
    }
    return newhead;
}

9.3 注意事项 

1.要考虑当原链表为空的情况；

2.复制链表然后再断开链表是一种解题思路。 

 

 

好了，今天就到这里，我们下一个知识点再见(*￣︶￣)~