链表OJ题

文章目录

• • 1. [链表的回文结构](https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking)
  • 2. [相交链表](https://leetcode.cn/problems/intersection-of-two-linked-lists/description/)
  • 3. 链表中倒数第k个结点
  • 4. [环形链表](https://leetcode.cn/problems/linked-list-cycle/description/)
  • 5. [环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/description/)
  • 6. [随机链表的复制](https://leetcode.cn/problems/copy-list-with-random-pointer/description/)

1. 链表的回文结构

因为单链表不能从后往前找节点，所以我们先找到中间节点，然后逆置，最后进行比较。

#include <stdio.h> #include <stdbool.h>  typedef struct ListNode { 	int val; 	struct ListNode* next; }ListNode;  struct ListNode* middleNode(struct ListNode* head) { 	ListNode* slow, * fast; 	slow = fast = head;  	while (fast && fast->next) 	{ 		slow = slow->next; 		fast = fast->next->next; 	}  	return slow; }  struct ListNode* reverseList(struct ListNode* head) { 	if (NULL == head) 	{ 		return head; 	}  	ListNode* n1, * n2, * n3; 	n1 = NULL, n2 = head, n3 = head->next;  	while (n2) 	{ 		n2->next = n1; 		n1 = n2; 		n2 = n3;  		if (n3) 		{ 			n3 = n3->next; 		} 	}  	return n1; }  bool chkPalindrome(ListNode* A) { 	ListNode* mid = middleNode(A); 	ListNode* rmid = reverseList(mid);  	while (A && rmid) 	{ 		if (A->val != rmid->val) 		{ 			return false; 		}  		A = A->next; 		rmid = rmid->next; 	}  	return true; } 

2. 相交链表

#include <stdio.h> #include <stdlib.h>  struct ListNode { 	int val; 	struct ListNode* next; };  struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { 	struct ListNode* curA = headA; 	struct ListNode* curB = headB;  	int lenA = 0;  	while (curA->next) 	{ 		++lenA; 		curA = curA->next; 	} 	 	int lenB = 0;  	while (curB->next) 	{ 		++lenB; 		curB = curB->next; 	}  	//不相交 	if (curA != curB) 	{ 		return NULL; 	}  	int gap = abs(lenA - lenB); 	//因为我们不知道A长还是B长，所以我们要用假设法，先假设A长，如果不对，再调换一下就行 	struct ListNode* longList = headA; 	struct ListNode* shortList = headB;  	if (lenB > lenA) 	{ 		longList = headB; 		shortList = headA; 	}  	//让长的先走gap步 	while (gap--) 	{ 		longList = longList->next; 	}  	//再同时走，找交点 	while (longList != shortList) 	{ 		longList = longList->next; 		shortList = shortList->next; 	}  	return longList; } 

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

思路2：

#include <stdio.h>  struct ListNode { 	int val; 	struct ListNoe* next; };  struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) { 	struct ListNode* slow = pListHead, * fast = pListHead;  	//fast先走k步 	while (k--) 	{ 		//k还没有减到0，链表已经空了，说明k大于链表的长度 		if (NULL == fast) 		{ 			return NULL; 		}  		fast = fast->next; 	}  	//slow和fast同时走，fast走到空，slow就是倒数第k个 	while (fast) 	{ 		slow = slow->next; 		fast = fast->next; 	}  	return slow; } 

4. 环形链表

#include <stdbool.h>  struct ListNode { 	int val; 	struct ListNode* next; };    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; } 

5. 环形链表 II

找入环点：

法一：

#include <stdio.h>  struct ListNode { 	int val; 	struct ListNode* next; };  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 (meet != head) 			{ 				meet = meet->next; 				head = head->next; 			}  			return meet; 		} 	}  	return NULL; } 

法二：

#include <stdio.h> #include <stdlib.h>  struct ListNode { 	int val; 	struct ListNode* next; };  struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { 	struct ListNode* curA = headA; 	struct ListNode* curB = headB;  	int lenA = 0;  	while (curA->next) 	{ 		++lenA; 		curA = curA->next; 	}  	int lenB = 0;  	while (curB->next) 	{ 		++lenB; 		curB = curB->next; 	}  	//不相交 	if (curA != curB) 	{ 		return NULL; 	}  	int gap = abs(lenA - lenB); 	struct ListNode* longList = headA; 	struct ListNode* shortList = headB;  	if (lenB > lenA) 	{ 		longList = headB; 		shortList = headA; 	}  	//让长的先走gap步 	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) 	{ 		slow = slow->next; 		fast = fast->next->next;  		if (slow == fast) 		{ 			struct ListNode* meet = slow; 			struct ListNode* headx = meet->next; 			meet->next = NULL;  			return getIntersectionNode(head, headx); 		} 	}  	return NULL; } 

6. 随机链表的复制

写代码的时候建议一边画细图，一边写：

#include <stdio.h> #include <stdlib.h>  struct Node {     int val;     struct Node *next;     struct Node *random; };  struct Node* copyRandomList(struct Node* head) {     struct Node* cur = head;      //拷贝节点插入原节点的后面      while (cur)     {         struct Node* copy = (struct Node*)malloc(sizeof(struct Node));         copy->val = cur->val;          //插入         copy->next = cur->next;         cur->next = copy;          //迭代         cur = cur->next->next;     }      //控制拷贝节点的random     cur = head;      while (cur)     {         struct Node* copy = cur->next;                  if (NULL == cur->random)         {             copy->random = NULL;         }         else         {             copy->random = cur->random->next;         }          //迭代         cur = cur->next->next;     }      //把copy节点解下来，链接成新链表     struct Node* copyhead = NULL, * tail = NULL;     cur = head;      while (cur)     {         struct Node* copy = cur->next;         struct Node* next = copy->next;          //尾插         if (NULL == tail)         {             copyhead = tail = copy;         }         else         {             tail->next = copy;             tail = tail->next;         }          cur->next = next;         cur = next;     }      return copyhead; }