C语言链表经典OJ题

链表经典OJ题

移除链表元素
链表的中间节点
反转链表
合并两个有序链表
分割链表

移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1 输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7 输出：[]

提示：
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

题目链接：link

本题不同于基本操作中的头删尾删等，因为头结点也有可能是要删掉的，那这个时候就比较麻烦了，所以我们最好是重新定义一个链表，遍历原链表不为val的节点，尾插在新链表中。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* create(int x)
{struct ListNode* new=(struct ListNode*)malloc(sizeof(struct ListNode));new->val=x;new->next=NULL;return new;
}
void PushBack(struct ListNode** pp,int x,struct ListNode** ppt)
{struct ListNode* new=create(x);if(*pp==NULL){*pp=new;*ppt=new;return;}(*ppt)->next=new;(*ppt)=(*ppt)->next;
}struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newhead=NULL;struct ListNode* tail=NULL;struct ListNode* cur=head;while(cur!=NULL){if(cur->val!=val)PushBack(&newhead,cur->val,&tail);cur=cur->next;}return newhead;
}

另外官方题解用了递归迭代的方式也很值得学习：

迭代：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* dummyHead=(struct ListNode*)malloc(sizeof(struct ListNode));dummyHead->next=head;struct ListNode* cur=dummyHead;while(cur->next!=NULL){if(cur->next->val==val)cur->next=cur->next->next;elsecur=cur->next;}return dummyHead->next;
}

递归的话，反正我是理解的不太好（每次都得画好久递归图才能理解呜呜呜）

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;
}

链表的中间节点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5] 输出：[3,4,5] 解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6] 输出：[4,5,6] 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

题目链接：link
这道题的思路是：设置两个指针，一个slow指针，一个fast指针，slow指针一次走一步，fast指针一次走两步，当fast或fast的next为空的时候，slow就是我们要找的中间节点。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode LN;
struct ListNode* middleNode(struct ListNode* head) {LN* slow=head;LN* fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

示例 1：

输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2] 输出：[2,1]

示例 3：

输入：head = [] 输出：[]

题目链接：link

这道题的思路非常精巧。
设立三个指针，n1，n2和n3，分别指向NULL，头结点和头结点的next。
当n2不为空的时候，将n2的next指向n1，然后将n3赋值给n2（这也是n3存在的意义，因为改变n2的next指针以后，n2就无法通过n2=n2->next语句访问到原链表的下一个指针了）n3=n3->next，n1=n2；

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode LN;
struct ListNode* reverseList(struct ListNode* head) {if(head==NULL)return NULL;if(head->next==NULL)return head;LN* n1=NULL;LN* n2=head;LN* n3=head->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3!=NULL)n3=n3->next;}return n1;
}

当然n3也可以不用一开始就定义，也可以在循环中当做一个临时变量：

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL;struct ListNode* curr = head;while (curr) {struct ListNode* next = curr->next;//在这里设置n3，就不用单独考虑head是否为空或者只有一个节点的情况了curr->next = prev;prev = curr;curr = next;}return prev;
}

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = [] 输出：[]

示例 3：

输入：l1 = [], l2 = [0] 输出：[0]

题目链接：link
设置四个指针，l1遍历链表1，l2遍历链表2，newhead是新链表头结点（哨兵位），newtail是新链表尾指针，l1和l2比较，谁小谁尾插到newtail后，然后向后走一位，没有尾插的不动，直到l1或l2有一方为空，再把没有遍历完的那个链表的剩余部分直接尾插到newtail后面。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode LN;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {LN* l1=list1;LN* l2=list2;LN* newhead=(LN*)malloc(sizeof(LN));LN* tail=newhead;if(l1==NULL&&l2==NULL)return NULL;while(l1&&l2){if(l1->val<=l2->val){tail->next=l1;l1=l1->next;}else{tail->next=l2;l2=l2->next;}tail=tail->next;}if(l1==NULL){tail->next=l2;}else{tail->next=l1;}return newhead->next;
}

分割链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你不需要保留每个分区中各节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2 输出：[1,2]

题目链接：link

大小链表法，新设两个链表一个放小的，一个放大的，然后最后把他们拼起来。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode LN;
struct ListNode* partition(struct ListNode* head, int x){LN* s=(LN*)malloc(sizeof(LN));LN* b=(LN*)malloc(sizeof(LN));LN* st=s;LN* bt=b;LN* cur=head;while(cur){if(cur->val<x){st->next=cur;st=st->next;}else{bt->next=cur;bt=bt->next;}cur=cur->next;}bt->next=NULL;st->next=b->next;}