【数据结构】详解11道链表OJ题（万字详解）_oj链表归并有哪些特殊情况

1. 移除链表元素

OJ链接

题目要求：

解析：

1. 法一：

• 两个指针：cur和prev。cur用来遍历，寻找需要被删除的结点；prev指向cur结点的前一个结点，用于删除,prev->next = cur->next，free(cur)(只有当头结点不为空且不需要删除时，才会用到prev指针)。
• 特殊情况1：链表为空，直接返回head。
• 特殊情况2：链表所有结点都需要被删除，（用不上指针prev）。

//code-1:
struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* cur = head;
    //1.特殊情况，链表为空
    if(cur == NULL)
        return head;
    
    //2.特殊情况，链表中的所有结点的val都等于目标值，需全部删除
    while(cur && cur->val == val)
    {
        struct ListNode* del = cur;
        cur = cur->next;
        free(del);
        //del是局部变量，不需要再置空
    }
    //更新头结点
    head = cur;
    //出2的循环时，要么cur为空，要么cur->val!=val

    //3.常规情况
    struct ListNode* prev = cur;
    //prev->val!=val
    if(prev)
    {
        
        cur = prev->next;
        //如果要删除，就删除cur结点
        while(cur)
        {
            //需要删除
            if(cur->val == val)
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
            else
            {
                prev = cur;
                cur = cur->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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

算法复杂度： 时间复杂度O(n)，空间复杂度O(1)。

2. 法二（推荐）：
   与法一类似，但代码简化许多。

• 两个指针：cur和prev。
• 直接用cur遍历。如果cur指向的结点不需要删除，让prev指向当前cur指向的结点，再让cur后移。
• 如果cur指向的结点需要删除，分情况。
  • 若当前cur指向的结点为头结点，则让head后移，然后删除当前cur结点。再更新cur指针。
  • 若当前cur指向的结点不为头结点，则按常规情况删除，prev->next = cur->next,free(cur)。再更新cur。

//code-2
struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;//指向要删除结点的上一个结点
    while(cur)
    {
        //需要删除当前结点
        if(cur->val == val)
        {
            //需要删除的结点是头结点
            if(cur == head)
            {
                head = head->next;
                free(cur);
                cur = head;
            }
            else//删除非头节点
            {
                //常规情况的删除
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {
            prev = cur;
            cur = cur->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
29
30
31
32
33

算法复杂度： 时间复杂度O(n)，空间复杂度O(1)。

3. 法三：

• 创建一个新链表。
• 用新链表存储不需要删除的结点（将原链表中不需要删除的结点链接到新链表中），删除原链表中需要删除的结点。
• 返回新链表。

//code-1: 不带哨兵位结点
struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* newHead, *tail;
    newHead = tail = NULL;

    struct ListNode* cur = head;

    while(cur)
    {
        if(cur->val != val)
        {
            if(tail == NULL)
            {
                newHead = tail = cur;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
        else
        {
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);//局部变量，不需要再置为空
        }
    }
    //新链表结尾置为空
    if(tail)//防止解引用空指针
        tail->next = NULL;
    return newHead;
}
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

//code-2: 带哨兵位结点   （推荐）
struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* cur = head;
    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    assert(guard);
    struct ListNode* tail = guard;
    while(cur)
    {
        if(cur->val != val)
        {
            tail->next = cur;
            cur = cur->next;
            tail = tail->next;
        }
        else
        {
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);
        }
    }
    //注意，一定要判断tail是否为空
    if(tail)
        tail->next = NULL;
    head = guard->next;
    free(guard);

    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

算法复杂度： 时间复杂度：O(n)，空间复杂度：O(1)。

2. 反转链表

OJ链接

题目要求：

解析：

1. 法一：

   • 将头结点后面的结点依次摘下，放到头结点前面。
   • 特殊情况不需要反转：链表为空或只有一个结点。
     

struct ListNode* reverseList(struct ListNode* head){
    //head为空，或head->next为空，就没必要反转
    if(!head || !head->next)
    {
        return head;
    }

    struct ListNode* cur = head->next;
    struct ListNode* newHead = head;
    while(cur)
    {
        head->next = cur->next;
        cur->next = newHead;
        newHead = cur;
        cur = head->next;
    }

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

算法复杂度： 时间：O(n)，空间O(1)。

2. 法二（推荐）：

   反转“指针”。
   

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* prev = NULL, *cur = head;
    while(cur)
    {
        struct ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}
1
2
3
4
5
6
7
8
9
10
11

算法复杂度： 时间：O(n)，空间：O(1)。

3. 链表的中间结点

OJ链接

题目要求：

解析：

• 快慢指针。
• slow一次走一步，fast一次走两步。
• 当fast为空或者fast->next为空时，结束。
• 此时，slow所指向的结点就是中间结点。

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast, *slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10

算法复杂度： 时间：O(n)，空间：O(1)。

4. 链表中倒数第k个结点

OJ链接

题目要求：

解析：

• 思路和上一题相似。
• 先让fast走k步，再同时走。
• 一般情况下：当fast为空时，结束。此时，slow所指向的结点即为所求结点。
• 特殊情况：k>链表长度。所以，需要判断结束条件，如果fast为空，但fast还没有走完k步，就返回NULL。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast, *slow;
    fast = slow = pListHead;
    
    //先让fast走k步
    while(fast && k--)
    {
        fast = fast->next;
    }
    //k>链表长度
    if(k > 0)
        return NULL;
    
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

算法复杂度： 时间：O(n)，空间：O(1)。

5. 合并两个有序链表

OJ链接

题目要求：

解析：

• 创建一个哨兵位结点guard，尾指针tail指向guard。
• 将原先两个链表中首结点（cur1和cur2）小的的结点链接到tail后面（相当于在tail后面链接了一个链表）。再让该结点后移。重复此过程。
• 当cur1和cur2中一个为空时（链表为空），结束。
• 将另一个不为空的链表链接到tail后面。
• 最后，返回guard->next。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    assert(guard);
    guard->next = NULL;
    struct ListNode* tail = guard;
    struct ListNode* cur1 = list1, *cur2 = list2;
    while(cur1 && cur2)
    {
        if(cur1->val < cur2->val)
        {
            tail->next = cur1;
            tail = tail->next;
            cur1 = cur1->next;
        }
        else
        {
            tail->next = cur2;
            tail = tail->next;
            cur2 = cur2->next;
        }
    }
    if(cur1)
    {
        tail->next = cur1;
    }
    if(cur2)
    {
        tail->next = cur2;
    }
    return guard->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

算法复杂度： 时间：O(n)，空间O(1)。

6. 链表分割

OJ链接

题目要求：

解析：

• 创建两个哨兵位结点GreaterGuard，LessGuard，及尾指针GreaterTail，LessTail指向哨兵位结点。
• 用cur（起初cur指向原链表头结点）遍历原链表。依次将小于x的结点链接到LessTail后面，不小于x的结点链接到GreaterTail后面。
• cur为空（即原链表为空）时，将GreaterGuard链表（不包括头结点）链接到LessGuard链表后面。
• 注意！！！将最终得到的链表的结尾置为NULL。
• 最后，返回最终得到的链表LessGuard（不包括头结点）。

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* LessGuard, *LessTail, *GreaterGuard, *GreaterTail;
        LessGuard = (ListNode*)malloc(sizeof(ListNode));
        GreaterGuard = (ListNode*)malloc(sizeof(ListNode));
        assert(LessGuard && GreaterGuard);
        LessTail = LessGuard;
        GreaterTail = GreaterGuard;
        GreaterTail->next = LessTail->next = NULL;//也可以不写
        
        ListNode* cur = pHead;
        while(cur)
        {
            if(cur->val < x)
            {
                LessTail->next = cur;
                LessTail = LessTail->next;
                
                //cur = cur->next;
            }
            else
            {
                GreaterTail->next = cur;
                GreaterTail = GreaterTail->next;
                //cur = cur->next;
            }
            cur = cur->next;
        }
        LessTail->next = GreaterGuard->next;
        GreaterTail->next = NULL;//注意，这一步不能省略
        
        pHead = LessGuard->next;
        free(LessGuard);
        free(GreaterGuard);
        
        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

算法复杂度： 时间：O(n)，空间O(1)。

7. 回文链表

OJ链接

题目要求：

解析：

• 找到中间结点。
• 反转中间结点之后的链表（包括中间结点）。
• 将原链表head和反转后的后半部分链表遍历比较。
• 循环结束条件：两链表当前遍历比较的结点只要有一个为NULL（考虑到原链表结点数为偶数时），就结束。
• 由于，找中间结点和反转链表前面已经论述过，便不再细述。
  

 //找中间结点
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast, *slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
//翻转链表
struct ListNode* reverseList(struct ListNode* head){
        struct ListNode* prev = NULL;
        struct ListNode* cur = head;
        while(cur)
        {
            struct ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
bool isPalindrome(struct ListNode* head){
    struct ListNode* mid = middleNode(head);
    struct ListNode* rmid = reverseList(mid);
    struct ListNode* cur = head;
    while(cur && rmid)
    {
        if(cur->val != rmid->val)
            return false;
        cur = cur->next;
        rmid = rmid->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

算法复杂度： 时间：O(n)，空间：O(1)。

8. 相交链表

OJ链接

题目要求：

解析：

• 判断两链表是否交叉。遍历两个链表headA和headB，若它们的尾结点地址相同，则交叉；否则，不交叉，返回NULL。
• 若链表交叉，找相交的起始结点。想办法让两个链表从各自与相交的起始结点距离相同的结点同时出发，当两链表用于遍历的结点cur的地址相同时，就找到了，返回该地址。
  • 在遍历链表的同时，计算两链表的长度len1和len2。得出长度之差gaplen，让长的链表先走gaplen步，两链表再同时走。
  • 当cur1和cur2相同时，返回当前地址。

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    if (!headA || !headB)
        return NULL;
    struct ListNode* cur1 = headA;
    struct ListNode* cur2 = headB;
    int len1 = 1;
    int len2 = 1;
    //找尾结点，并记录链表长度
    while (cur1->next)
    {
        cur1 = cur1->next;
        len1++;
    }
    while (cur2->next)
    {
        cur2 = cur2->next;
        len2++;
    }
    //两链表不交叉
    if (cur1 != cur2)
    {
        return NULL;
    }
    //
    struct ListNode* LongList = headA;
    struct ListNode* ShortList = headB;
    if (len1 < len2)
    {
        LongList = headB;
        ShortList = headA;
    }
    //长度的差值
    int gap = abs(len1 - len2);
    //长的先走差值步
    while (gap--)
    {
        LongList = LongList->next;
    }
    //同时走
    while (LongList != ShortList)
    {
        LongList = LongList->next;
        ShortList = ShortList->next;
    }
    
    return LongList;
}
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

算法复杂度： 时间：O(N)，空间：O(1)

9.环形链表

OJ链接
题目要求：

解析：

• 快慢指针。初始slow和fast都指向头结点。
• slow和fast同时走，slow走一步，fast走两步。
• 如果链表有环，那么两指针一定会在换种相遇。否则，fast先走到链表的末尾，循环结束。程序结束。

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow, *fast;
    slow = fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        //相遇即带环
        if(fast == slow)
            return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

算法复杂度： 时间：O(N)，空间：O(1)

拓展：

1. 为什么满指针每次走一步，快指针每次走两步可以？

   假设链表带环，那么最终慢指针和快指针都会进环。快指针先进环，慢指针后进环。最坏的情况是：慢指针刚进环时，快指针恰好在慢指针前面一步（环内），此时两者之间的距离是环的长度-1。慢指针走一步，快指针走两步，（可以根据相对运动的角度理解：慢指针不动，快指针走一步），每次两指针之间的距离都会-1，那么最终就一定会追上。

2. 快指针每次走3步、4步、… … 、n步可以吗？

   假定快指针每次走3步，环的长度为C。慢指针进环时，两指针之间的距离是X。每次循环（走）两指针之间的距离X减2。

   • 如果进环时，环长C是偶数，两指针之间的距离X也是偶数，最终，会追上（fast==slow）；
   • 如果进环时，环长C是偶数，两指针之间的距离X是奇数，每次距离减2，最终，两指针会错过（fast ==slow->next），此时两指针之间的距离X是C-1（奇数），每次距离减2，就会永远错过，不会相遇（fast ==slow）。

10.环形链表 II

OJ链接
题目要求：

解析：

1. 法一（推荐）：

   • 思路与上一题类似。
   • 先判断是否有环（按照上一题的思路）。
   • 若有环：定义一个新指针meet=slow（相遇结点位置），cur=head（头结点）。两指针同时走，当两指针相遇（cur==meet），相遇的结点即为入环的第一个结点。
     

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast = head, *slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
        {
            struct ListNode* meet = slow;
            struct ListNode* cur = head;
            //一个指针从头走，同时另一个指针从相遇点走，两者会在入环的第一个结点相遇
            while(meet != cur)
            {
                cur = cur->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

算法复杂度： 时间：O(N)，空间：O(1)。

2. 法二：

• 同样，先判断是否有环。
• 若有环：将环从相遇点断开，转换成求相交链表的第一个公共结点问题（本文第8题）

//求相交链表的第一个公共结点
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    if (!headA || !headB)
        return NULL;
    struct ListNode* cur1 = headA;
    struct ListNode* cur2 = headB;
    int len1 = 1;
    int len2 = 1;
    //找尾结点，并记录链表长度
    while (cur1->next)
    {
        cur1 = cur1->next;
        len1++;
    }
    while (cur2->next)
    {
        cur2 = cur2->next;
        len2++;
    }
    //两链表不交叉
    if (cur1 != cur2)
    {
        return NULL;
    }
    //
    struct ListNode* LongList = headA;
    struct ListNode* ShortList = headB;
    if (len1 < len2)
    {
        LongList = headB;
        ShortList = headA;
    }
    //长度的差值
    int gap = abs(len1 - len2);
    //长的先走差值步
    while (gap--)
    {
        LongList = LongList->next;
    }
    //同时走
    while (LongList != ShortList)
    {
        LongList = LongList->next;
        ShortList = ShortList->next;
    }
    
    return LongList;
}
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow = head, *fast = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            struct ListNode* meet = slow;
            struct ListNode* next = meet->next;
            //将环断开，变成相交链表问题
            meet->next = NULL;
            struct ListNode* entryNode = getIntersectionNode(head, next);
            meet->next = next;
            return entryNode;
        }
    }
    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
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

算法复杂度： 时间：O(N)，空间：O(1)

11. 复制带随机指针的链表

OJ链接
题目要求：

解析：

1. 复制结点。依次创建同类型的结点，插入到原链表中的两个结点之间。
2. 改变复制结点的random。
   • 若原链表中对应结点（被复制的结点）的random指向NULL，则复制结点的random也指向NULL。
   • 否则，让复制结点的random指向原链表中对应结点（被复制的结点）的random->next。
3. 恢复原链表，链接新链表。将原链表的next指针恢复，并且将复制结点链接起来，组成一个原链表的复制链表。
   

struct Node* copyRandomList(struct Node* head) {
   struct Node* cur = head;
   struct Node* copy = NULL;
   struct Node* next = NULL;
   //复制
   while(cur)
   {
       copy = (struct Node*)malloc(sizeof(struct Node));
       assert(copy);
       copy->val = cur->val;
       next = cur->next;

       cur->next = copy;
       copy->next = next;
       
       //后移
       cur = next;
   }
   //链接random指针
   cur = head;
   while(cur)
   {
       copy = cur->next;
       if(cur->random == NULL)
           copy->random = NULL;
       else
           copy->random = cur->random->next;

       cur = cur->next->next;
   }
   //还原原链表
   struct Node* copyhead = NULL, *copytail = NULL;
   cur = head;
   while(cur)
   {
       copy = cur->next;
       next = copy->next;
       //取copy结点 尾插
       if(copytail == NULL)
       {
           copyhead = copytail = copy;
       }
       else
       {
           copytail->next = copy;
           copytail = copytail->next;
       }
       //恢复原链表
       cur->next = next;

       cur = next;
   }

   return copyhead;
}
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

算法复杂度： 时间：O(N)，空间：O(1)。