单链表oj (上)，详细的过程分析，每道题有多种解题思路，一定会有所收获

🧸🧸🧸各位巨佬大家好，我是猪皮兄弟🧸🧸🧸

这里是下面要讲的知识内容🥳🥳🥳

🚒前言

链表中，单链表的oj是面试中最常考察的问题，单链表的解题逻辑也很有意思，下面一起来看看吧！

---

一、移除链表元素

leetcode移除链表元素

三种思路
1.需要一个prev指针，指向被删除结点的前一个，然后进行遍历
2.设置一个新的头，对需要保留的结点进行链接
3.malloc一个头节点，比方法一好控制一点

方法一

struct ListNode* removeElements(struct ListNode* head, int val){
    if(head==NULL)
    return NULL;
    struct ListNode*prev=NULL,*cur=head;
    while(cur)
    {
        if(cur->val==val)
        {
            if(prev==NULL)
            {
                head=cur->next;
                free(cur);
                cur=head;
            }
            else
            {
                prev->next=cur->next;
                free(cur);
                cur=prev->next;
            }

        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

方法二

struct ListNode* removeElements(struct ListNode* head, int val){
    if(head==NULL)
        return NULL;
    struct ListNode*newhead=NULL;
    struct ListNode*tail=newhead;
    struct ListNode*cur=head;
    while(cur)
    {
        if(cur->val!=val)
        {
            if(newhead==NULL)
            {
                newhead=tail=cur;
            }
            else 
            {
                tail->next=cur;
                tail=cur;
            }
        }
        cur=cur->next;
    }
    if(newhead!=NULL)
    tail->next=NULL;
    return newhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

方法三

struct ListNode* removeElements(struct ListNode* head, int val){
    if(head==NULL)
    return NULL;
    struct ListNode* Node=(struct ListNode*)malloc(sizeof(struct ListNode));
    Node->next=head;
    struct ListNode*prev=Node,*cur=head;
    while(cur)
    {
        if(cur->val==val)
        {
            if(cur==head)
            {
                head=cur->next;
                free(cur);
                cur=head;
            }
            else
            {
                prev->next=cur->next;
                free(cur);
                cur=prev->next;
            }

        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    free(Node);
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

二、反转链表

leetcode反转链表

两种思路
1.malloc一个头结点，然后设置三个临时的指针变量进行控制
2.设置一个新的头，遍历链表，每次都取下来连接到新的上，就可以实现反向

方法一

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL||head->next==NULL)
    return head;
    struct ListNode* Node=(struct ListNode*)malloc(sizeof(struct ListNode));
    Node->next=head;
    struct ListNode*n1,*n2,*n3;
    n1=Node;
    n2=head;
    n3=head->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n2)//控制边界条件
        n3=n3->next;
    }
    head->next=NULL;
    head=n1;
    free(Node);
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法二

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL||head->next==NULL)
    return head;
    struct ListNode*cur,*next,*newhead;
    cur=head;
    next=cur->next;
    newhead=NULL;
    while(cur)
    {
        if(head==cur)
        cur->next=newhead;
        else
        {
            cur->next=newhead;
        }
        newhead=cur;
        cur=next;
        if(cur)
        next=next->next;
    }
    return newhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

三、倒数第n个结点

nowcoder倒数第n个结点

三种思路
1.两次遍历，计算链表长度来减去k次就是需要执行的长度
2.反转链表再遍历k个结点
3.快慢指针

方法一

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    int count=0;
    struct ListNode*cur=pListHead;
    while(cur)
    {
        cur=cur->next;
        count++;
    }
    int runNum=count-k;
    count=0;
    cur=pListHead;
    while(cur)
    {
        if(count==runNum)
        {
            break;
        }
        count++;
        cur=cur->next;
    }
    return cur;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法二
就是反转一下链表再遍历k个就可以了，我就不写了
方法三
利用快慢指针

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode*fast,*slow;
    fast=pListHead;
    slow=NULL;
    int count=0;
    while(count!=k&&fast)
    {
        fast=fast->next;
        count++;
    }
    if(count==k)
        slow=pListHead;
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

四、合并有序链表

遍历两个链表即可

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(!list1)
    return list2;
    if(!list2)
    return list1;
    struct ListNode*head;
    if(list1->val<list2->val)
    {
        head=list1;
        list1=list1->next;
    }
    else
    {
        head=list2;
        list2=list2->next;
    }
    struct ListNode*tail=head;
    while(list1&&list2)
    {
        if(list1->val<=list2->val)
        {
            tail->next=list1;
            tail=list1;
            list1=list1->next;
        }
        else
        {
            tail->next=list2;
            tail=list2;
            list2=list2->next;
        }

    }
    if(list1)
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

五、小总结

单链表的oj在面试当中出现频率是很高的，单链表有些操作也是很玄幻，跟着我一起来做题吧，后面还会继续更新🥳🥳🥳