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;
        else
            cur=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;
    
}