链表OJ题（1）

淡淡的烟草味﹌ 2023-10-13 09:41 42阅读 0赞

**目录**

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

二、 反转一个单链表。

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

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

--------------------

You only live once.

--------------------

### 一 、删除链表中等于给定值 **val** 的所有节点。 ###

[https://leetcode.cn/problems/remove-linked-list-elements/description/][https_leetcode.cn_problems_remove-linked-list-elements_description]

**代码展示：**

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

**思路**：(1)首先给出判断cur是否是空的，不是空的之后，判断是否有val，有的话就判断是否在头部，是的话一种情况，不是的话，又是一种情况。（2）第一种情况，题意所给出的情况；第二种情况，中间连续个value（前两种可以合并）；第三种情况，一开始就出现6或者连续个6；第四种情况：空的

> **注意**：（1）每一道题，都要考虑多种情况，不仅仅是力扣所给出的情况。
> 
> （2）编译错误：代码错误；执行错误：逻辑错误

### 二、 反转一个单链表。 ###

[https://leetcode.cn/problems/reverse-linked-list/][https_leetcode.cn_problems_reverse-linked-list]

**代码1展示：（思路一）**

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

**代码2展示：（思路二）**

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

**思路一**：指向前一个

**思路二**：头插，创建一个新的链表，newlist，为空。先保存旧链表cur的next，然后,cur->next指向新的链表，新的链表head指向cur,以此重复，一直到cur为空停止。

> **注意**：能写循环的话，不写递归

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

[https://leetcode.cn/problems/middle-of-the-linked-list/description/][https_leetcode.cn_problems_middle-of-the-linked-list_description]

**代码展示**：

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

**思路**：首先定义两个指针，一个（slow）每次走一个，另一个(fast)每次走两个数据，奇数个时：当fast->next等于NULL时，slow刚好是中间。偶数个时，当fast等于NULL时，slow刚好是中间值的第二个。

> 注意：while (fast && (fast ->next))；当两个条件有关系的时候，要注意前后，这个代码条件前后颠倒就会发生错误。

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

[https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_529d3ae5a407492994ad2a246518148a_tpId_13_tqId_11167_rp_2_ru_activity_oj_qru_ta_coding-interviews_question-ranking]

**代码展示**：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
        // write code here
        struct ListNode* slow = pListHead;
        struct ListNode* fast = pListHead;
        for (int i = 0; i < k; i++)
        {
            //k大于链表的长度
            if (fast == NULL)
            {
                return NULL;
            }
            fast = fast->next;
        }
        while (fast != NULL)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }

**思路**：首先定义两个指针，fast和slow;先让fast走K个，然后slow和fat一起走，当fast为NULL时，slow就是倒数第k个。

> **注意**:K大于链表

[https_leetcode.cn_problems_remove-linked-list-elements_description]: https://leetcode.cn/problems/remove-linked-list-elements/description/
[https_leetcode.cn_problems_reverse-linked-list]: https://leetcode.cn/problems/reverse-linked-list/
[https_leetcode.cn_problems_middle-of-the-linked-list_description]: https://leetcode.cn/problems/middle-of-the-linked-list/description/
[https_www.nowcoder.com_practice_529d3ae5a407492994ad2a246518148a_tpId_13_tqId_11167_rp_2_ru_activity_oj_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking