【数据结构】链表经典题目

柔情只为你懂 2024-04-01 18:34 98阅读 0赞

#### 文章目录 ####

*   *   *   *  移除链表元素
             *  合并两个有序链表
             *  链表的中间节点
             *  链表中的倒数第k个结点
             *  反转链表
             *  链表分割
             *  链表的回文结构
             *  相交链表
             *  环形链表
             *  环形链表II(找到如环的节点)
             *  复制带随机指针的链表

##### [移除链表元素][Link 1] #####

> ![image-20221107152834165][]
> 
> 思路：先要判断这个链表是不是空链表，如果是空链表就直接返回NULL，就可以
> 
> 代码：
> 
>     struct ListNode* removeElements(struct ListNode* head, int val){
>          
>         if(head == NULL)
>         {
>          
>             return NULL;
>         }
>         struct ListNode* cur = head;
>         struct ListNode* newnode, *tail;
>         newnode = tail = NULL;
>         while(cur != NULL)
>         {
>          
>             if(cur->val != val)
>             {
>          
>                 if(tail == NULL)
>                 {
>          
>                     newnode = tail = cur;
>                 }
>                 else 
>                 {
>          
>                     tail->next = cur;
>                     tail = tail->next;
>                 }
>                 cur = cur->next;
>             }
>             else
>             {
>          
>                 struct ListNode* next = cur->next;
>                 free(cur);
>                 cur = next;
>             }
>         }
>         if(tail)
>         {
>          
>             tail->next = NULL;
>         }
>         return newnode;
>     }
> 
> 注意：这个题最后需要注意的是`tail`的下一个应该也是`NULL`，否则就有可能将最后一个链表连接。
> 
> ![image-20221107153412182][]

##### [合并两个有序链表][Link 2] #####

> ![image-20221107161447520][]
> 
> 思路：重新用一个新的链表头来表示节点，如果小于的数就加入到链表当中。
> 
> 代码：
> 
>     struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
>          
>         if(list1 == NULL) {
>          
>             return list2;
>         }
>         if(list2 == NULL) {
>          
>             return list1;
>         }
>         struct ListNode* head, *tail;
>         head = tail = NULL;
>         while(list1 && list2) {
>          
>             if(list1->val < list2->val) {
>          
>                 if(tail == NULL) {
>          
>                     head = tail = list1;
>                 }else {
>          
>                     tail->next = list1;
>                     tail = tail->next;
>                 }
>                 list1 = list1->next;
>             }else {
>          
>                 if(tail == NULL) {
>          
>                     head = tail = list2;
>                 }else {
>          
>                     tail->next = list2;
>                     tail = tail->next;
>                 }
>                 list2 = list2->next;
>             }
>         }
>         if(list1) {
>          
>             tail->next = list1;
>         }
>         if(list2) {
>          
>             tail->next = list2;
>         }
>         return head;
>     }

##### [链表的中间节点][Link 3] #####

> ![image-20221108153220143][]
> 
> 思路：这个题目只需要根据速度差，一个指针的速度是另一个指针速度的二倍，当快的指针到达终点的时候，慢指针刚好到达中间节点。
> 
> 代码：
> 
>     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;
>     }

##### [链表中的倒数第k个结点][k] #####

> ![image-20221108154323978][]
> 
> 思路：先让快的链表走k步，然后两个指针一起往后移动，如果快的指针到达最后，慢的指针就是最后的结果。
> 
> 代码：
> 
>     struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
>          
>        // write code here
>        struct ListNode *fast, *slow;
>        fast = slow = pListHead;
>        while(k) {
>          
>            if(fast == NULL) {
>          
>                return NULL;
>            }
>            fast = fast->next;
>            k --;
>        }
>        while(fast) {
>          
>            fast = fast->next;
>            slow = slow->next;
>        }
>        return slow;
>     }

##### [反转链表][Link 4] #####

> ![image-20221111173758852][]
> 
> ![image-20221111173913597][]
> 
> 代码：
> 
>     struct ListNode* reverseList(struct ListNode* head){
>          
>         if(head == NULL) {
>          
>             return NULL;
>         }
>         struct ListNode* n1, *n2, *n3;
>         n1 = NULL;
>         n2 = head;
>         n3 = n2->next;
>         while(n2) {
>          
>             n2->next = n1;
>             n1 = n2;
>             n2 = n3;
>             if(n3) {
>          
>                 n3 = n3->next;
>             }
>         }
>         return n1;
>     }

##### [链表分割][Link 5] #####

> ![image-20221112155443108][]
> 
> 对于最后一个数字，还有不同的情况考虑：
> 
> ![image-20221112155805638][]
> 
> 代码：
> 
>     class Partition {
>          
>     public:
>         ListNode* partition(ListNode* pHead, int x) {
>          
>             // write code here
>             struct ListNode* lessHead, *lessTail, *greaterHead, *greaterTail;
>             lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
>             greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
>             lessTail->next = greaterTail->next = NULL;
>             struct ListNode* cur = pHead;
>             while(cur) {
>          
>                 if(cur->val < x) {
>          
>                     lessTail->next = cur;
>                     lessTail = lessTail->next;
>                 }else {
>          
>                     greaterTail->next = cur;
>                     greaterTail = greaterTail->next;
>                 }
>                 cur = cur->next;
>             }
>             lessTail->next = greaterHead->next;
>             greaterTail->next = NULL;
>             pHead = lessHead->next;
>             free(lessHead);
>             free(greaterHead);
>             return pHead;
>         }
>     };

##### 链表的回文结构 #####

> ![image-20221114151032185][]
> 
> 思路：直接找到中间节点，然后反转中间节点到最后的链表就可以。
> 
> 代码：
> 
>     struct ListNode* findMid(struct ListNode* A) {
>          
>         struct ListNode* slow = A, *fast = A;
>         while(fast && fast->next) {
>          
>             slow = slow->next;
>             fast = fast->next->next;
>         }
>         return slow;
>     }
>     
>     struct ListNode* reverse(struct ListNode* mid) {
>          
>         struct ListNode* n1 = NULL, *n2 = mid, *n3 = n2->next;
>         while(n2) {
>          
>             n2->next = n1;
>             n1 = n2;
>             n2 = n3;
>             if(n3) {
>          
>                 n3 = n3->next;
>             }
>         }
>         return n1;
>     }
>     
>     class PalindromeList {
>          
>     public:
>         bool chkPalindrome(ListNode* A) {
>          
>             // write code here
>             struct ListNode* mid = findMid(A);
>             struct ListNode* rhead = reverse(mid);
>             while(A && rhead) {
>          
>                 if(A->val != rhead->val) {
>          
>                     return false;
>                 }
>                 A = A->next;
>                 rhead = rhead->next;
>             }
>             return true;
>         }
>     };

##### [相交链表][Link 6] #####

> ![image-20221114152805524][]
> 
> 思路：找到两个其中长的一个链表，然后走差值步，一起走看是否有相等的地址。
> 
> 代码：
> 
>     struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
>          
>             struct ListNode* curA = headA, *curB = headB;
>             int lenA = 0, lenB = 0;
>         	//分别找到链表A和链表B的长度
>             while(curA) {
>          
>                 lenA ++;
>                 curA = curA->next;
>             }
>             while(curB) {
>          
>                 lenB ++;
>                 curB = curB->next;
>             }
>         	//如果最后不相等，则绝对不存在公共节点
>         	//如果相等，则一定存在公共节点
>             if(curA != curB) {
>          
>                 return NULL;
>             }
>             int gap = abs(lenA - lenB);
>         	//假设A>B
>             struct ListNode* LongList = headA, *ShortList = headB;
>             if(lenB > lenA) {
>          
>                 LongList = headB;
>                 ShortList = headA;
>             }
>             while(gap --) {
>          
>                 LongList = LongList->next;
>             }
>             while(LongList != ShortList) {
>          
>                 LongList = LongList->next;
>                 ShortList = ShortList->next;
>             }
>             return LongList;
>     }

##### [环形链表][Link 7] #####

> ![image-20221114153632036][]
> 
> 思路：两个指针，一个指针每次跑一步，另一个指针每次跑两步，如果有环两个指针肯定能够相遇。
> 
> 代码：
> 
>     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;
>     }
> 
> ![image-20221114154758953][]

##### [环形链表II(找到如环的节点)][II] #####

> ![image-20221114155737474][]
> 
> ![image-20221114155742679][]
> 
> 结论：让一个指针从链表的起始位置开始遍历链表，同时让一个指针从判环相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
> 
> 代码：
> 
>     struct ListNode *detectCycle(struct ListNode *head) {
>          
>         struct ListNode* slow = head, *fast = head;
>         while(fast && fast->next) {
>          
>             slow = slow->next;
>             fast = fast->next->next;
>             if(slow == fast) {
>          
>                 struct ListNode* meet = slow;
>                 while(head != meet) {
>          
>                     head = head->next;
>                     meet = meet->next;
>                 }
>                 return head;
>             }
>         }
>         return NULL;
>     }

##### [复制带随机指针的链表][Link 8] #####

> ![image-20221114163044019][]
> 
> 思路：
> 
> 1.  拷贝节点在源节点的后面
> 
> ![image-20221114164111905][]
> 
> 代码实现：
> 
>     struct Node* copyRandomList(struct Node* head) {
>          
>     	struct Node* cur = head;
>         while(cur) {
>          
>             struct Node* next = cur->next;
>             struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
>             copy->val = cur->val;
>             cur->next = copy;
>             copy->next = next;
>             cur = next;
>         }
>     }
> 
> 1.  设置拷贝节点的random
> 
> ![image-20221114164648509][]
> 
> 代码实现：
> 
>     struct Node* copyRandomList(struct Node* head) {
>          
>     	struct Node* cur = head;
>         while(cur) {
>          
>             struct Node* next = cur->next;
>             struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
>             copy->val = cur->val;
>             cur->next = copy;
>             copy->next = next;
>             cur = next;
>         }
>         //设置拷贝节点的random
>         cur = head;
>         while(cur) {
>          
>             struct Node* copy = cur->next;
>             if(cur->next == NULL) {
>          
>                 copy->random = NULL;
>             }else {
>          
>                 copy->random = cur->random->next;
>             }
>             cur = cur->next->next;
>         }
>     }
> 
> 1.  拷贝节点解下来，连接组成拷贝链表
> 
> 代码实现：
> 
>     struct Node* copyRandomList(struct Node* head) {
>          
>     	struct Node* cur = head;
>         while(cur) {
>          
>             struct Node* next = cur->next;
>             struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
>             copy->val = cur->val;
>             cur->next = copy;
>             copy->next = next;
>             cur = next;
>         }
>         cur = head;
>         while(cur) {
>          
>             struct Node* copy = cur->next;
>             if(cur->random == NULL) {
>          
>                 copy->random = NULL;
>             }else {
>          
>                 copy->random = cur->random->next;
>             }
>             cur = cur->next->next;
>         }
>         cur = head;
>         struct Node* copyHead = NULL, *copyTail = NULL;
>         while(cur) {
>          
>             struct Node* copy = cur->next;
>             struct Node* next = copy->next;
>             cur->next = next;
>             if(copyTail == NULL) {
>          
>                 copyHead = copyTail = copy;
>             }else {
>          
>                 copyTail->next = copy;
>                 copyTail = copyTail->next;
>             }
>             cur = next;
>         }
>         return copyHead;
>     }

[Link 1]: https://leetcode.cn/problems/remove-linked-list-elements/description/
[image-20221107152834165]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e08f9d0661c1429ca290b23766357248.png
[image-20221107153412182]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/85bfe2cb562b400dad90ce13967067bb.png
[Link 2]: https://leetcode.cn/problems/merge-two-sorted-lists/description/
[image-20221107161447520]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/346d14d08b324b76ab86955d3496c4ff.png
[Link 3]: https://leetcode.cn/problems/middle-of-the-linked-list/description/
[image-20221108153220143]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4ee11edf2ae54cae865b858625c100ee.png
[k]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[image-20221108154323978]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/04f22e8111794e4a8cd1744670890faa.png
[Link 4]: https://leetcode.cn/problems/reverse-linked-list/description/
[image-20221111173758852]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5b6f75d489a94944827f3fa562fef2fe.png
[image-20221111173913597]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/fe9468aa7b014e239cde360c05753579.png
[Link 5]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[image-20221112155443108]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ca13c96fd2ae45ae94de10fffbc69607.png
[image-20221112155805638]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e4588425fc7c42cca49f2c6fe900ff75.png
[image-20221114151032185]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/33284c825b3b45efb62f79011e2bdd0a.png
[Link 6]: https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
[image-20221114152805524]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5272ddc6133e4a739da52ba4ac1869d0.png
[Link 7]: https://leetcode.cn/problems/linked-list-cycle/description/
[image-20221114153632036]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/36b84704e5a4447185c7f43e1de641b0.png
[image-20221114154758953]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ba35eab08b4b42cbadb363f8da1ab292.png
[II]: https://leetcode.cn/problems/linked-list-cycle-ii/description/
[image-20221114155737474]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d205829cc6014800a62abfc28dcfb33b.png
[image-20221114155742679]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/8d05dd59d97540e5ac5855386ac7e2ba.png
[Link 8]: https://leetcode.cn/problems/copy-list-with-random-pointer/description/
[image-20221114163044019]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/7406b0de70c94eafa0a0ff1ef0117a90.png
[image-20221114164111905]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/007e39fca4e24463955d70a2eff312e3.png
[image-20221114164648509]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/1e09b78615e6487ba32d063fca7870ce.png