【数据结构】LeetCode单链表经典题型_struct listnode* head

目录

1.移除链表元素​编辑

2.反转链表 ​编辑

 3.链表的中间结点​编辑

 4.链表中倒数第K个结点​编辑

 5.合并两个有序链表​编辑

 6.链表分割

 7.链表的回文结构​编辑

 8.相交链表​编辑

9.环形链表​编辑

10.返回环形链表的起始结点​编辑

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

1.移除链表元素

首先来简单分析一下，这里和上一篇单链表的任意位置删除大同小异，比较简单，注意删除后链表的链接即可，删除之前首先定义一个next记住下一个节点的地址，以免删除过后找不到链接的点，还有一种方法是先将需要删除的val前一个结点和后一个结点连接起来，再删除。

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    while(cur)
    {
        struct ListNode* next = cur->next;
        if(cur->val == val)
        {
            if(prev == NULL)
            {
                free(cur);
                cur = next;
                head = next;
            }
            else
            {
                prev->next = next;
                free(cur);
                cur = next;
            }
        }
        else
        {
            prev=cur;
            cur = cur->next;
        }
    }
    return head;
}

2.反转链表 

这里的思路还是很容易想到的，我们给一个头结点phead，然后从此链表的头结点开始给一个cur，将cur的next存起来，然后将cur->next指向头结点，随后将cur和next向后移一个节点，以此类推，当next为NULL的时候结束。画图给大家演示一下 

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL || head->next == NULL)
        return head;
    struct ListNode* n1 = NULL, *n2 = head,*n3 = head->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3 != NULL)
            n3 = n3->next;
    } 
    return n1;
}

 3.链表的中间结点

 这道题比较有意思，这里我们需要用到的思想是快慢指针，slow指针一次走一步，fast指针一次走两步，是slow的两倍，当fast走到最后的时候，那么slow的路程就该是fast的一半，这样就可以找到中间结点了，需要注意的是，我们判定fast结束的标志是fast==NULL还是fast->next==NULL呢

 

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

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

这题和上面中间结点大同小异，我们也可以用快慢指针的思想，当fast指针先走K步，然后slow和fast同时一步一步的走，那么他们之间的距离就会始终保持在K，当fast走到最后一个结点时，skow就应该走到倒数第K个结点了 

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    if(pListHead == NULL)
        return NULL;
    else
    {
        struct ListNode* slow = pListHead;
        struct ListNode* fast = pListHead;
        while(k--)
        {
            if(fast == NULL)
                return NULL;
            fast = fast->next;
        }
        while(fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
}

 5.合并两个有序链表

 思路：这里我的做题思路是给一个头结点head然后两个链表的头设置为cur1和cur2将cur1和cur2比较小的链接在head后面，然后向后走一个结点，再比较，直到有一个链表的cur走到尾了过后将剩余的链接在后面就行了，画图演示一下 

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* tail = head;
    if(list1 == NULL)
        return list2;
    else if(list2 == NULL)
        return list1;
    while(list1 && list2)
    {
        if(list1->val < list2->val)
        {
            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
    }
    if(list1)
    {
        tail->next = list1;
    }
    else if(list2)
    {
        tail->next = list2;
    }
    struct ListNode* Plist = head->next;
    free(head);
    head = NULL;
    return Plist;
}

 6.链表分割

 

 思路：因为不能改变分割后的顺序，给大家用实例画图来讲解

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* greaterHead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* lessHead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* lessTail = (ListNode*)malloc(sizeof(ListNode));
        ListNode* greaterTail = (ListNode*)malloc(sizeof(ListNode));
        ListNode* cur = pHead;
        lessHead = lessTail;
        greaterHead = greaterTail;
        lessTail->next = NULL;
        greaterTail->next = NULL;
        while(cur)
        {
            if(cur->val < x)
            {
                lessTail->next = cur;
                lessTail = cur;
            }
            else
            {
                greaterTail->next = cur;
                greaterTail = cur;
            }
            cur = cur->next;
        }
        lessTail->next = greaterHead->next;
        //将最后一个值置为空，避免出现回环情况
        greaterTail->next = NULL;
        free(greaterHead);
        ListNode* node = lessHead->next;
        free(lessHead);
        return node;
    }
};

 7.链表的回文结构

 思路：回文结构就相当于链表以中间结点为对称轴左右对称，我们只需要将中间结点以后的部分翻转过来然后和前面的部分进行比较，如果相等就返回true，不相等就返回false。而找中间结点和翻转链表我们上面讲过，可以直接拿过来用。

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL || head->next == NULL)
        return head;
    struct ListNode* n1 = NULL, *n2 = head,*n3 = head->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3 != NULL)
            n3 = n3->next;
    } 
    return n1;
}
 
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        if(A == NULL)
            return false;
        //1.先找到中间结点
        struct ListNode* mid = middleNode(A);
        //2.翻转后面的部分
        struct ListNode* midAfter = reverseList(mid);
        while(midAfter && A)
        {
            if((A->val) != (midAfter->val))
            {
                return false;
            }
            else
            {
                A = A->next;
                midAfter = midAfter->next;
            }
        }
        return true;
    }
};

 8.相交链表

 思路：由于A链表和B链表的长度可不同，所以我们第一步先将两个链表遍历一遍，求出两个链表的长度，然后让长的链表先走差距不，这样他们剩下的路程都是相同的，没走一遍比较他们的next是否相同（不能比较val，因为val可能存在相同的值），，若相同则返回结点，该结点为其实结点，当两个链表走到空都没有，则返回NULL。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA == NULL || headB == NULL)
        return NULL;
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    int lenA = 0;
    int lenB = 0;
    while(curA)
    {
        curA = curA->next;
        lenA++;
    }
    while(curB)
    {
        curB = curB->next;
        lenB++;
    }
    //先将A链表视为长的，B链表视为短的
    struct ListNode* longList = headA, *shortList = headB;
    int gap = abs(lenA - lenB);
    //判断A如果比B短就交换一下
    if(lenA < lenB)
    {
        longList = headB;
        shortList = headA;
    }
    //长的先走差距步
    while(gap--)
    {
        longList = longList->next;
    }
    //再同时走判断指向的next的地址是否一样
    while(longList && shortList)
    {
        if(longList == shortList)
        {
            return longList;
        }
        else
        {
            longList = longList->next;
            shortList = shortList->next;
        }
 
    }
    return NULL;
}

9.环形链表

思路：这里我们也用到快慢指针，slow走一步，fast走两步，当fast进化时slow走了一半，当slow进环后fast也在环里面，假设他们之间的差距为N，他们每次的距离都为-1最终会相遇，则说明次链表有环，若没有环，则fast会首先走到空，就返回false。 

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow = head, *fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            return true;
        }
    }
    return false;
}

10.返回环形链表的起始结点

 思路：上面我们用到了快慢指针来证明链表是否有环，这里我们要返回进入环的起始结点，这里的思路是当他们相遇时，一个指针从相遇点开始走，一个指针走头结点开始走，他们相遇的点就是环的起始点，这个思路非常妙，下面用图给大家推演一遍。因为L=C-X，所以可以从meet和head同时走且在环起始点相遇。

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast, *slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            struct ListNode* meet = fast;
            while(meet != head)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

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

 题目描述：这道题的意思就是自己开创一个链表与上面一样，完全复制出来。

思路：第一步：先从复制next，从头head开始，没走过一个链表就开创一个结点链接在次结点后面，相当于在次位置插一个结点，然后将next链接到原链表，并且赋值

 第二步：从原链表cur开始，cur指向的random就是我们需要找的random，因为是复制新的链表，所以联系应该在我们copy的链表里，因为第一步每个原链表后面开创了一个结点，所以当前的cur指向的random的next也就是cur->random->next就是我们需要链接的结点。以copy的13结点的random为例copy的13的random等于原链表13的random也就是原链表的7的next，也就是copy的7,这样就将copy之间的random链接起来了。

 第三步：也就是断开copy链表与原链表的联系，并且将copy的链表链接在一起。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL)
            return NULL;
        struct Node* cur = head;
        //1.开辟的新节点放在原结点后面，串联起来
        while(cur)
        {
            struct Node* next = cur->next;
            struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
            copy->val = cur->val;
            copy->next = cur->next;
            cur->next = copy;
            cur = next;
        }
        //2.处理random（将copy的random = copy->next->random）
        cur = head;
        while(cur)
        {
            struct Node* copy = cur->next;
            if(cur->random == NULL)
                copy->random = NULL;
            else
                copy->random = cur->random->next;
            cur = copy->next;
        }
        //3.回复原链表，将copy的链表串联起来
        //开辟一个哨兵位的头结点
        struct Node* copyhead, *copytail;
        copyhead = copytail = (struct Node*)malloc(sizeof(struct Node));
        copyhead = copytail;
        cur = head;
        while(cur)
        {
            struct Node* copy = cur->next;
            struct Node* next = copy->next;
            copytail->next = copy;
            copytail = copytail->next;
            cur->next = next;
            cur = next;
        }
        struct Node* guard = copyhead;
        copyhead = copyhead->next;
        free(guard);
        return copyhead;
    }
};

---