一、移除链表元素

题目:传送门

题目描述

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

示例

示例 1：

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

输出：[1,2,3,4,5]

示例2:

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

输出：[]

思路:

1.创建一个cur指针=head,用于代替head往后遍历寻找结点的val值为val的目标结点.

2.创建一个prev指针,初始化为NULL,用于跟在cur后面,负责改变要删除的目标结点的前驱的next.

3.当cur为目标结点时,使目标结点的前驱(prev)的next跳过目标结点(cur),指向目标结点的下一个节点(cur->next).

4.释放掉cur所指向的目标结点(此时prev->next为cur的下一个结点),由于cur被释放掉了,cur要继续往后走的时候,需要借助prev即(cur=prev->next)

5.直到cur=NULL结束循环.

图解:

代码:

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode*cur=head;//代替head遍历链表
    struct ListNode*prev=NULL;//记录目标结点的前驱,并使其的next跳过目标结点
    while(cur)//循环条件是cur不指向空
    {
        if(cur->val!=val)//如果不是目标结点
        {
            prev=cur;//cur往后走之前记录位置
            cur=cur->next;//cur往后走
        }
        else
        {
            if(prev==NULL)//如果第一个节点就等于val,这时的prev为NULL
            {
              //用于头删
                head=cur->next;//记录头结点的后继
                free(cur);//释放头结点
                cur=head;//使头指针指向第二个结点
            }
            else 
            {
            //此时cur为要删除的目标结点
              prev->next=cur->next;//使得目标结点的前驱的next指向目标结点的下一个结点
              free(cur);//释放掉要删除的结点
              cur=prev->next;//接触prev使cur往后走.
            }
        }
    }
    return head;//最后返回头结点
}

二、反转链表

题目:传送门

题目描述:

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

示例

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

输出：[5,4,3,2,1]

输入：head = [1,2]

输出：[2,1]

思路:

1.创建一个记录前驱的指针prev,初始值应为NULL,即第一个结点改变后指向的前驱

2.创建一个遍历链表的指针cur,作用是改变其指向的结点的next,初始值应该为head即第一个要改变的结点.

3.创建一个记录后继的指针tail,初始值为,head->next,用于记录后继,否则cur不知道后面的路在哪里了.

指针创建好后,使用cur->next = prev,改变cur结点的next指向.

更新前驱:prev = cur

cur继续往后走:cur = tail

更新后继:tail = tail->next

注意,循环体设计的条件是,cur指向NULL停止,这是,tail已经为空,所以要限制一下条件.只有当还有后继即tail不为空时,才保留后继.

图解:

代码:

struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)//防止传入空链表
    {
        return NULL;
    }
    struct ListNode* prev = NULL;//记录前驱结点
    struct ListNode* cur = head;//遍历链表
    struct ListNode* tail = head->next;//记录后继结点
    while (cur)
    {
        cur->next = prev;//使得结点的next指向它的前驱
        prev = cur;//更新前驱
        cur = tail;//cur往后走
        if(tail)tail = tail->next;//更新后继
    }
    return prev;
}

三、链表的中间结点

题目描述:

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

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

示例:

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

输出：[3,4,5]

解释：链表只有一个中间结点，值为 3 。

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

输出：[4,5,6]

解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

常规思路:

创建指针cur代替head遍历链表

先遍历一遍链表,计算链表的长度,得到length.

使cur重新赋值为head

使cur往后走length/2步便可以得到中间结点.

最后返回cur

代码1:

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*cur=head;
    int length=0;
    while(cur!=NULL)//计算链表的长度
    {
        cur=cur->next;
        length++;
    }
    length=length/2;
    cur=head;//重新赋值
    while(length--)//往后走length/2步
    {
        cur=cur->next;
    }
    return cur;//返回中间结点
}

思路2:快慢指针

定义一个slow(慢指针)指针

定义一个fast(快指针)指针

两个指针都是从head指向的结点出发,fast一次走两步,slow一次走一步,当fast走向NULL的时候,slow刚好走到中间结点处.

建议画图分析链表的长度为奇数和偶数情况.

代码2:

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(fast&&fast->next)
    {
        fast=(fast->next)->next;
        slow=slow->next;
    }
    return slow;
}

结语:

对于数据结构初学者,链表的oj题对于帮助掌握链表还是很有好处的.可以帮助自己更好的理解和掌握链表.

还有,快慢指针的使用是一个很好的思想,在很多情况下时可以给我们带来便利,不要仅限于快指针永远都只会走两步的固定思想哦!