单链表在线OJ题二（详解+图解）

1.在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针

本题的意思是要删除链表中重复出现的节点，然后返回删除重复节点后的链表。
我们可以直接用一个哨兵位以便于观察链表的情况，然后用前后指针来解决这个问题。如果当前节点cur的值与其当前节点的next的所存储的值相等（且cur的next不为空），cur就变成cur的next，然后用while循环进行判断，如果cur的val与cur的next的val相等且cur的next不为空，就然后cur往后移动，直到遇到不相同的情况，跳出循环后cur还要记得移动到cur的next；然后再将前指针prev的next置为cur，这样就可以将相等的节点省略。当cur的next为空或者cur的值与cur的next的值不相等时，就直接先将prev置为cur，再将cur往后移动变成cur的next。最后返回哨兵位vpead的next，就是存储了有效数据的首节点，就可以返回整个删除后的单链表了。

完整代码如下：

struct ListNode *deleteDuplication(struct ListNode *pHead)
{
    struct ListNode *vHead;
    vHead = (struct ListNode *)malloc(sizeof(struct ListNode));
    vHead->next = pHead;
    //定义虚头结点方便边界情况讨论
    struct ListNode *pre, *cur;
    pre = vHead, cur = pHead;
    while (cur)
    {
        if (cur->next && cur->val == cur->next->val)
        {
            cur = cur->next;
            while (cur->next && cur->val == cur->next->val)
                cur = cur->next;
        //当遇到与下一节点值相同时,cur推进到最后一个重复的数字处
        //本数字舍去,pre连接到下一个
            cur = cur->next;
            pre->next = cur;
        }
        //遇到与下一节点值不同或者是没有下一节点时,pre移动到此处,cur继续后移
        else if(!cur->next || cur->val != cur->next->val)
        {
            pre = cur;
            cur = cur->next;
        }
    }
    return vHead->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

2.对链表进行插入排序

本题也要使用到哨兵位，用哨兵位的next最后可以返回排序完后的链表，并且使用前后指针，进行大小比较，若是逆序则用前后指针的关系进行交换即可
完整代码如下：

struct ListNode *insertionSortList(struct ListNode *head) 
{
    if (head == NULL) 
        return head;
    struct ListNode *dummyHead = malloc(sizeof(struct ListNode));
    dummyHead->val = 0;
    dummyHead->next = head;//哨兵位
    struct ListNode *lastSorted = head;
    struct ListNode *curr = head->next;
    while (curr != NULL) {
        if (lastSorted->val <= curr->val) 
        {
            lastSorted = lastSorted->next;
        } 
        else 
        {
            struct ListNode *prev = dummyHead;
            while (prev->next->val <= curr->val) 
            {
                prev = prev->next;
            }
            lastSorted->next = curr->next;
            curr->next = prev->next;
            prev->next = curr;
        }
        curr = lastSorted->next;
    }
    return dummyHead->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

3.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

本题的意思很简单，就是一个判断链表是否有环的问题，如果有环就返回那个节点，看图就明白了，就是最后一个节点的next会连接到前面的节点，就是有环。
到这里我们就要有一个大概的思路了–快慢指针！
我们用慢指针slow一次走一步，fast一次走两步，到最后他们就一定会相遇，因为他们移动的差距只有一步一次追一步就必然会相遇。当slow和fast相遇时，我们再定义一个新指针从头节点开始往后移动，同时将slow或者fast往后移动，当这个新指针与slow或者fast相等时这个节点就返回这个节点，这个节点就是链表尾链接到链表的节点。

完整代码如下：

struct ListNode* detectCycle(struct ListNode* head) 
{
    struct ListNode *slow = head, *fast = head;
    while (fast != NULL) 
    {
        slow = slow->next;
        if (fast->next == NULL) 
        {
            return NULL;
        }
        fast = fast->next->next;
        if (fast == slow) 
        {
            struct ListNode* ptr = head;
            while (ptr != slow) 
            {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }
    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

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

有了上一题的思路，这一题就很简单了，让slow指针和fast指针分别往后移动，slow一次走一步，fast一次走两步，如果二者能相遇（相遇即slow指针会与fast指针相等），那就是链表中有环，否则无环；

完整代码如下：

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

5.输入两个链表，找出它们的第一个公共结点

其实这一题也很简单
首先我们得判断这个链表是否会相交，如果相交，那么两个链表的尾节点就会相等，若不想等就直接返回NULL指针
其次我们分别求两个链表的长度，用tail尾指针遍历求出lenA,lenB
然后我们用lenA-lenB相减的绝对值就能得出两个链表的长度差gap，让长的链表先走gap步，然后短的链表再和长的链表一起走，当两个链表的指针节点相等时，这个节点就是两个链表相遇的节点，返回这个节点即可

完整代码如下：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* tailA=headA;
    struct ListNode* tailB=headB;
    int lenA=1;
    int lenB=1;
    while(tailA)
    {
        tailA=tailA->next;
        lenA++;
    }
    while(tailB)
    {
        tailB=tailB->next;
        lenB++;
    }
    if(tailA!=tailB)
    {
        return NULL;
    }
    int gap=abs(lenA-lenB);
    struct ListNode* longlist=headA;
    struct ListNode* shortlist=headB;
    if(lenAnext;
    }
    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

我们再OJ题的解题中可以发现，快慢指针的解题思路是非常重要的，大家可以多去做一点题 ！
好了，今天的分享到这里就结束了，谢谢大家的支持！