目录
① 203.移除链表元素
② 206.反转链表
③ 876.链表的中间节点
④ 返回倒数第k个节点（面试题）
⑤ 21.合并两个有序链表
⑥ 160.相交链表
⑦ 138.随机链表的复制（深拷贝）
① 203.移除链表元素
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {ListNode*newHead = NULL, *newTail = NULL;ListNode*pcur = head;while(pcur != NULL){if(pcur->val != val){if(newHead == NULL){//将新链表的头尾指针指向原链表头节点newHead = newTail = pcur;}else{newTail->next = pcur;newTail = newTail->next;}}pcur = pcur->next;}if(newTail != NULL){newTail->next = NULL;} return newHead;
}
② 206.反转链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL;//哨兵位struct ListNode* cur = head;//头节点while (cur) {// 哨兵位（prev） 节点1（cur） 节点2（cur->next）struct ListNode* next = cur->next;//创建一个中间节点//开始改变链表的方向cur->next = prev;//节点2先指向节点1的前一个节点prev = cur;//哨兵位往后移动cur = next;//节点1向后移动}return prev;
}
③ 876.链表的中间节点
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/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;
}
④ 返回倒数第k个节点（面试题）
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
int kthToLast(struct ListNode* head, int k) {struct ListNode *fast = head, *slow = head;//本题采用的是相对法：// fast先运动k个节点// 假设该链表的节点个数是 m+k 个// 则先走k个节点，剩下fast指针到null指针时，即走了m个节点// 此时，slow指针就剩余k个节点while(k--){fast = fast->next;}while(fast != NULL){slow = slow->next;fast = fast->next; }return slow->val;
}
⑤ 21.合并两个有序链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}struct ListNode* l1 = list1;struct ListNode* l2 = list2;struct ListNode* newHead, *newTail; newHead = newTail = NULL;while(l1 && l2){//比大小if(l1->val < l2->val){if(newHead == NULL){newHead = newTail = l1;}else{newTail->next = l1;newTail = newTail->next;}l1 = l1->next;}else{if(newHead == NULL){newHead = newTail = l2;}else{newTail->next = l2;newTail = newTail->next;}l2 = l2->next;}}if(l1){newTail->next = l1;}if(l2){newTail->next = l2;}return newHead;
}
⑥ 160.相交链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA = headA, *curB = headB;int lenA = 1, lenB = 1;while(curA->next){curA = curA->next;++lenA;}while(curB->next){curB = curB->next;++lenB;}if(curA != curB){return NULL;}//假设法int gap = abs(lenA - lenB);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;}
⑦ 138.随机链表的复制（深拷贝）
/*** Definition for a Node.* 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链表插入原链表中copy->next = cur->next;cur->next = copy;//cur向后移动cur = copy->next;}//将copy链表中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;}cur = head;struct Node* copyHead = NULL,* copyTail =NULL;while(cur){struct Node* copy = cur->next;if(copyTail == NULL){copyHead = copyTail = copy;}else{copyTail->next = copy;copyTail = copyTail->next;}//cur向后移动cur = copy->next;}return copyHead;
}
