一、移除链表元素

题目:传送门

题目描述

给你一个链表的头节点 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题对于帮助掌握链表还是很有好处的.可以帮助自己更好的理解和掌握链表.

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