【C语言】LeetCode的链表题复习

前言

• 因为大一学习链表时草草了事，对于链表的一些算法题做得非常的少，因而在大二上学期这段时间学习数据结构时，链表-树-图的基础知识越来越差，更不用说做树、图的算法题了。所以在上周完成iOS方向的一个项目后，这段自由支配的时间我选择用来重新巩固基础，毕竟以后不论实习还是工作面试还是会考算法的。
• 以下挑了这个周做的一些链表基础但很重要的题目

LeetCode 206. 反转链表

LeetCode 206. 反转链表

• 方法一：迭代法

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* p = NULL;
    struct ListNode* cur = head;
    if (!cur) {
        return head;
    }
    while (cur) {
        struct ListNode* pNext = cur->next;
        cur->next = p;
        p = cur;
        cur = pNext;
    }
    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 方法二：递归法

若从节点 Nk+1到Nm已经被反转，而我们正处于 Nk，我们希望Nk+1的下一个节点指向Nk,
所以Nk.next.next = Nk;
需要注意的是N1的下一个节点必须指向 ∅。如果忽略了这一点，链表中可能会产生环。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head){
    if (!head || !head->next) {
        return head;
    }
    struct ListNode* realHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;

    return realHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode 143. 重排链表

LeetCode 143. 重排链表

• 方法一：我用的方法时间复杂度有点高，我是通过双指针，第一个指针停留在如上图的2位置的上一个节点，然后第二个指针从第一个指针停留处向后遍历直到第二个指针的next->next为NULL时，说明需要将第二个指针所指向节点移到第一个指针的后面。插入完毕后，第一个指针向后移两次（为什么是两次？因为刚才新插入了一个节点），然后循环如上，直至第一个指针的next为空。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

void reorderList(struct ListNode* head){
    struct ListNode* pSlow = head;
    struct ListNode* pFast = head;
    if (!head->next || !head->next || !head->next->next) {
        return head;
    }
    while (pSlow->next && pSlow->next->next) {
        pFast = pSlow;
        while (pFast->next->next) {
            pFast = pFast->next;
        }
        struct ListNode* pTemp1 = pFast->next;
        pFast->next = pFast->next->next;
        struct ListNode* pTemp3 = pSlow->next;
        pSlow->next = pTemp1;
        pTemp1->next = pTemp3;
        pSlow = pSlow->next->next;
    }
    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

• 官方方法：

方法二：线性表
方法三：寻找链表中点 + 链表逆序 + 合并链表
官方做法

LeetCode 142. 环形链表 II

LeetCode 142. 环形链表 II

• 题解

这道题在看了题解后发现它主要体现了数学的思想，通过快慢指针相遇后所走的路程之间的关系列出了一个等式，慢指针继续开始走，然后推出用第三个指针从head开始走，当慢指针恰好也走到索引处，第三个指针也走到索引处，就可判断相遇的位置就是索要的索引节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *pSlow = head;
    struct ListNode *pFast = head;
    if (!pSlow || !pSlow->next) {
        return NULL;
    }
    int flag = 0;
    while (flag == 0 || pSlow != pFast) {
        if (!pFast || !pFast->next){
            return NULL;
        }
        flag = 1;
        pFast = pFast->next->next;
        pSlow = pSlow->next;
    }
    struct ListNode *ptr = head;
    while (ptr != pSlow) {
        ptr = ptr->next;
        pSlow = pSlow->next;
    }
    return pSlow;
}
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

• 下周继续练习LeetCode，学习一下关于树的算法题