链表相关oj题

1.Leetcode203 移除链表元素

解题思路：从头节点开始进行元素删除，每删除一个元素，需要重新链接节点

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode*dummyhead=malloc(sizeof(struct ListNode));dummyhead->next=head;struct ListNode*temp=dummyhead;while(temp->next!=NULL){if(temp->next->val==val){temp->next=temp->next->next;}else {temp=temp->next;}}return dummyhead->next;}

2.Leetcode206 反转链表

解题思路： 此题一般常用的方法有两种，三指针翻转法和头插法

1. 三指针翻转法：记录连续的三个节点，原地修改节点指向
   

struct ListNode* reverseList(struct ListNode* head) {if(head == NULL || head->next == NULL)return head;struct ListNode* n1, *n2, *n3;n1 = head;n2 = n1->next;n3 = n2->next;n1->next = NULL;//中间节点不为空，继续修改指向while(n2){//中间节点指向反转n2->next = n1;//更新三个连续的节点n1 = n2;n2 = n3;if(n3)n3 = n3->next;}//返回新的头return n1;
}

2. 头插法：每一个节点都进行头插

// 取节点头插的思想完成逆置
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* newhead = NULL;struct ListNode* cur = head;while(cur){struct ListNode* next = cur->next;//头插新节点，更新头cur->next = newhead;newhead = cur;cur = next;}return newhead;
}

3.Leetcode876 链表的中间节点

解题思路：
通过快慢指针找到中间节点，快指针每次走两步，慢指针每次走一步，当快指针走到结尾的时候，慢指针正好走到中间位置

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

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

解题思路：
快慢指针法 fast, slow, 首先让fast先走k步，然后fast,slow同时走，fast走到末尾时，slow走到倒数第k个节点。

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

5.Leetcode 21 合并两个有序链表

解题思路：
此题可以先创建一个空链表，然后依次从两个有序链表中选取最小的进行尾插操作进行合并。

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

6.牛客：链表分割

解题思路
创建两个链表，分别存放小于x的节点和大于等于x的节点，分别进行尾插，最后再将两个链表并成一个

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode*ghead,*gtail;struct ListNode*lhead,*ltail;ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode *cur=pHead;while(cur){if(cur->val<x){gtail->next=cur;gtail=gtail->next;}else {ltail->next=cur;ltail=ltail->next;}cur=cur->next;}gtail->next=lhead->next;  //小的尾节点接到大的哨兵头上ltail->next=NULL;  //防止出现环pHead=ghead->next;free(ghead);free(lhead);return pHead;}
};

7.牛客：链表的回文结构

解题思路：
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。

class PalindromeList {public:bool chkPalindrome(ListNode* A) {struct ListNode* mid=middleNode(A);  //找到链表的中间节点struct ListNode* rA=reverseList(mid);    //逆置中间节点以后的节点while(mid&&rA){if(A->val!=rA->val)return false;A=A->next;rA=rA->next;}return true;}struct ListNode* reverseList(struct ListNode* head) {struct ListNode* tail = NULL, *cur = head;while (cur) {struct ListNode* next = cur->next;cur->next = tail; //头插tail = cur; //移动tailcur = next;}return tail;}struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow, *fast;slow = fast = head;while (fast &&fast->next) { //两个都非空才能循环，有一个是空就结束循环slow = slow->next;fast = fast->next->next;}return slow;}
};

8.Leetcode160 相交链表

解题思路：
此题可以先计算出两个链表的长度，让长的链表先走相差的长度，然后两个链表同时走，直到遇到相同的节点，即为第一个公共节点

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* tailA=headA,*tailB=headB;int lenA=1,lenB=1;while(tailA->next)  //分别求出来两个链表的长度{tailA=tailA->next;lenA++;}while(tailB->next)  //分别求出来两个链表的长度{tailB=tailB->next;lenB++;}if(tailA!=tailB)  //链表最后一个节点的地址不相等，说明不相交return NULL;//让长的链表先走 长度差 的步数int gap=abs(lenA-lenB);struct ListNode*longlist=headA,*shortlist=headB;if(lenA<lenB) {longlist=headB;shortlist=headA;}//让长的链表先走 长度差 的步数while(gap--){longlist=longlist->next;}//然后两个链表同时走，比较节点地址是否相等while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;}

9.Leetcode141 环形链表

解题思路：
定义快慢指针fast,slow, 如果链表确实有环，fast指针一定会在环内追上slow指针。

bool hasCycle(struct ListNode *head) {struct ListNode* slow,*fast;slow=fast=head;//快慢指针while(fast&&fast->next){//慢指针走一步，快指针走两步，如果快指针等于慢指针说明有环slow=slow->next;fast=fast->next->next;if(slow==fast)return true;}return false;
}

10.Leetcode142 环形链表Ⅱ

解题思路：

如果链表存在环，则fast和slow会在环内相遇

1. 定义相遇点到入口点的距离为X
2. 定义环的长度为C
3. 定义头到入口的距离为L

fast在slow进入环之后一圈内追上slow,则会得知：

1. slow所走的步数为:L + X
2. fast所走的步数为：L + X + N * C

并且fast所走的步数为slow的两倍，故：
2*(L + X) = L + X + N * C 即： L = N * C - X
所以从相遇点开始slow继续走，让一个指针从头开始走，两者相遇点即为入口节点

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=slow;struct ListNode*phead=head;while(meet!=phead){meet=meet->next;phead=phead->next;}return meet;}}return NULL;
}

Leetcode 138复制带随机指针的链表

解题思路：
1.拷贝节点链接在原节点的后面

2.拷贝节点的random指向原节点random的next

3.拷贝节点接下来，链接成新节点，原链表恢复原样

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* cur=head;//1.插入拷贝节点在原节点的后面while(cur){struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;struct Node* next=cur->next;cur->next=copy;copy->next=next;cur=next;}//2.拷贝节点的random指向原节点random的nextcur=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;}//3.拷贝节点接下来，链接成新节点，并且恢复原链表struct Node* copyhead=NULL ,*copytail=NULL;cur=head;while(cur){struct Node* copy=cur->next;struct Node* next=copy->next;if(copyhead==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}cur->next=next;cur=next;}return copyhead;}

---

本篇到此结束，码文不易，还请多多支持哦！