【Leetcode刷题（数据结构）】：单向链表_c 语言 刷 leetcode

1 删除链表中等于给定值 val 的所有节点

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

输入：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
输出：[ ]
思路如下

见详细代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode*prev=NULL;
    struct ListNode*cur=head;
    while(cur)
    {
        if(cur->val==val)
        {
            if(cur==head)
            {
                head=cur->next;
                cur=head;
            }
            // head=cur->next;
            // cur=head;
            else
            {
                prev->next=cur->next;
                cur=prev->next;
            }
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
        // else
        // {
        //     prev->next=cur->next;
        //     cur=prev->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
32
33
34
35
36
37
38
39
40

上述注释掉的代码是我在写的时候犯的错误，大家也可以试着自己写写看会不会和我犯同样的错误
如果有其他思路可以随意发表意见！

2 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
给你单链表的头结点head ，请你找出并返回链表的中间结点
如果有两个中间结点，则返回第二个中间结点

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

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为3和4，返回第二个结点
思路
大部分人呢第一个想到的就是先去遍历一遍链表计算出链表的长度—然后再次遍历一遍链表找到链表的的中间结点
但是如果是在面试的时候面试官让你只能遍历一次那你应该怎么处理呢？
这里运用的是快慢指针的相对速度
这时候我们可以考虑用快慢指针来作答

fast走两步，slow走一步，刚好天时地利人和走到了中间结点的位置
详细代码

/**
 * 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3 输入一个链表，输出该链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点
描述
输入一个链表，输出该链表中倒数第k个结点
示例1
输入：1,{1,2,3,4,5}
返回值：{5}

思路一致
这里运用的快慢指针的相对距离
解法一

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
   struct ListNode* cur=pListHead;
   int count=0;//建立一个计数器
   if(pListHead==NULL)//如果链表为空，则返回空指针
   {
    return NULL;
   }
   while(cur)//循环遍历链表，求出链表的长度
   {
    cur=cur->next;
    count++;
   }
   if(k>0&&k<=count)//对k值的合理性进行判断
   {
    int pos=count-k;//求出循环的次数
   while(pos)
   {
    pListHead=pListHead->next;
    pos--;
   }
   return pListHead;//找到就返回目标结点
   }
   return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

解法二

//计数法 时间复杂度：0（n） 空间：O（1）
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    // write code here
    if(pListHead == NULL || pListHead->next == NULL)
    //若链表没有结点或只有一个结点时返回（第二条件不必须）
    {
        return pListHead;
    }
    int nodenums = 0;//记录总结点数（第一次遍历)
    int returnnums = 0;//第二次遍历（每经过一次结点，前置+1)用于排查K结点
    struct ListNode* cur = pListHead;
    while(cur != NULL)//计数遍历
    {
        nodenums++;
        cur = cur->next;
    }
     if(k>nodenums)//如果k>总结点数，则代表不存在这一结点，返回空
    {
        return NULL;
    }
    struct ListNode* pwe = pListHead;
    while(pwe != NULL)//第二次遍历，寻找倒数K点
    {
        ++returnnums;//每经过一个结点就+1
         if(nodenums-returnnums < k)
        //如果结点总数减去当前结点数小于K，那么这个结点就是倒数K结点；
        {
            break;
        }
        pwe = pwe->next;
    }
    return pwe;
}
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

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

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

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [ ], l2 = [ ]
输出：[ ]
示例 3：
输入：l1 = [ ], l2 = [0]
输出：[0]
思路


本质上是结构体指针的地址和成员变量next的相互赋值，这里也涉及到了链表的尾插，直接套用就可以了，前提是掌握好了链表的增删查改基本逻辑
代码演示

/**
 * 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;
    }
    else if(list2==NULL)
    {
        return list1;
    }
    //定义一个head和tail
    //head和tail最初都置为NULL
    //tail=tail->next
    //尾部插入
    struct ListNode*head=NULL;
    struct ListNode*tail=NULL;
    while(list1&&list2)
    {
        //取小的尾部插入
        if(list1->val<list2->val)
        {
            if(tail==NULL)
            {
                head=tail=list1;
                //tail=tail->next;
            }
            else
            {
                tail->next=list1;
                tail=tail->next;
            }
            list1=list1->next;   
        }
        else
        {
            if(tail==NULL)
            {
                head=tail=list2;
            }
            else
            {
                tail->next=list2;
                tail=tail->next;
            }
            list2=list2->next; 
        }
    }
    if(list1)
    {
        tail->next=list1;
    }
    else 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63