文章目录

• 前言
• 1. 移除链表元素
• 2. 反转链表
• 3. 链表的中间结点
• 4. 合并两个有序链表
• 5. 链表分割
• 6. 链表的回文结构
• 7. 相交链表
• 8. 环形链表
• 9. 复制带随机指针的链表

前言

学完链表后，刷一些基础的链表题有助于提高对链表的理解与运用。

1. 移除链表元素

题目链接：移除链表元素

思路：递归/迭代
递归：

迭代:

1. 创建新指针ans
2. 遍历链表head，将不是值不是val的结点尾插在ans链表上
3. 返回ans

//递归
struct ListNode* removeElements(struct ListNode* head, int val) {if (head == NULL) {return head;}head->next = removeElements(head->next, val);return head->val == val ? head->next : head;
}
//迭代
void SLTPushBack(struct ListNode** pphead, int x)
{//情况：链表为空或不为空struct ListNode* newnode = malloc(sizeof(struct ListNode));assert(newnode != NULL);newnode->val = x;newnode->next = NULL;if (*pphead == NULL){*pphead = newnode;}else{struct ListNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}
struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* ans = NULL;while(head) {if (head->val != val) {SLTPushBack(&ans, head->val);}head = head->next;}return ans;
}

2. 反转链表

题目链接：反转链表

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head, *newhead = NULL;while (cur) {struct ListNode* next = cur->next;cur->next = newhead;newhead = cur;cur = next;}return newhead;}
}

3. 链表的中间结点

题目链接：链表的中间结点

思路：快慢指针
快指针(fast)一次走两步，慢指针(slow)一次走一步
注意：奇、偶

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个结点

4. 合并两个有序链表

题目链接：合并两个有序链表

本题用递归很简单解决。
官方的动图解答非常清晰，建议看官方的解答

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1 == NULL) {return list2;}if(list2 == NULL) {return list1;}if(list1->val <= list2->val) {list1->next = mergeTwoLists(list1->next, list2);return list1;}else {list2->next = mergeTwoLists(list1, list2->next);return list2;}
}

5. 链表分割

题目链接：链表分割

思路：
创立两个头节点，一个放比x小的结点，另一个放不比x小的结点
遍历原链表，将每个结点尾插在对应的头结点后面
最后将两个头节点后面的链表合在一起

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* com_low, *com_up, *Tail_low, *Tail_up;com_low = Tail_low = (struct ListNode*)malloc(sizeof(struct ListNode));com_up = Tail_up = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = pHead;while(cur) {if(cur->val < x) {Tail_low->next = cur;Tail_low = Tail_low->next;}else {Tail_up->next = cur;Tail_up = Tail_up->next;}cur = cur->next;}Tail_low->next = com_up->next;Tail_up->next = NULL;struct ListNode* ans = com_low->next;free(com_up);free(com_low);return ans;}
};
}

6. 链表的回文结构

题目链接：链表的回文结构

思路：需要先做2，3题。不能反转整个链表。

class PalindromeList {public:struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head, *newhead = NULL;while (cur) {struct ListNode* next = cur->next;cur->next = newhead;newhead = cur;cur = next;}return newhead;}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;}bool chkPalindrome(ListNode* head) {struct ListNode* mid = middleNode(head);struct ListNode* rhead = reverseList(mid);while(rhead) {if(head->val != rhead->val) {return false;}head = head->next;rhead = rhead->next;}return true;}
};

7. 相交链表

题目链接：相交链表

思路：
分别遍历A,B链表
使用countA, countB分别记录对应的结点数
查看尾节点是否一致
若一致则继续，比较countA,countB,让长的链表多走|countA-countB|步，再同时继续向后，直到二者相等
不一致则返回NULL

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* tailA, *tailB, *curA, *curB;int countA = 0, countB = 0;curA = tailA = headA;curB = tailB = headB;while(tailA->next) {tailA = tailA->next;countA++;}while(tailB->next) {tailB = tailB->next;countB++;}if(tailA != tailB) {return NULL;}else {while(countA > countB) {curA = curA->next;countA--;}while(countB > countA) {curB = curB->next;countB--;}while(curA != curB) {curA = curA->next;curB = curB->next;}return curA;}
}

8. 环形链表

题目链接：环形链表

思路

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

同类题：环形链表2

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

题目链接：复制带随机指针的链表

思路

struct Node* copyRandomList(struct Node* head) {//1. 拷贝节点放在原节点的后面struct Node* cur = head, *next = NULL;while(cur) {struct Node* copy_node = (struct Node*)malloc(sizeof(struct Node));next = cur->next;cur->next = copy_node;copy_node->val = cur->val;copy_node->next = next;cur = next;}//2. 对拷贝节点的random赋值cur = head;while(cur) {if(cur->random == NULL) {cur->next->random = NULL;}else {cur->next->random = cur->random->next;}cur = cur->next->next;}//3. 取下拷贝节点并链接，恢复原链表struct Node* tail, *ans = NULL;int flag = 1;cur = head;while(cur) {next = cur->next;//恢复原链表cur->next = next->next;if(flag) {ans = tail = next;next->next = NULL;flag = !flag;}else {//链接拷贝节点tail->next = next;tail = next;tail->next = NULL;}cur = cur->next;}return ans;
}