- 一.反转链表
- 二.查找并返回链表的中间节点
- 三、删除链表中等于给定值 val 的所有节点
- 四.链表中倒数第k个结点
- 五.合并两个有序链表
- 六.以给定值x为基准将链表分割成两部分
- 七.删除链表重复节点
- 八.判断回文链表
- 九.输入两个链表,找出它们的第一个公共结点
- 十.判断链表是否有环
- 十一.返回链表开始入环的第一个节点
一.反转链表
思路演示
代码实现
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev=head;
//排除链表没有节点元素的情况
if(head==null)
{
return null;
}
//链表只有一个节点的时候直接反回这个节点
if(head.next==null)
{
return head;
}
ListNode cur=prev.next;
ListNode newhead=null;
while(cur!=null)
{
ListNode curNext=cur.next;
//确保cur已经遍历到最后一个节点了
if(curNext==null)
{
newhead=cur;
}
cur.next=prev;
prev=cur;
cur=curNext;
}
head.next=null;
return newhead;
}
}
大家也来试试吧:题目链接(反转链表:电脑打开)
二.查找并返回链表的中间节点方法:快慢指针
定义快指针fast,慢指针slow,让fast和slow从同一个起点开始出发。fast一次走两步,slow一次走一步,当fast走到最后一个节点的时候,slow刚好处于中间节点(fast比slow多走了一半的路程)
代码实现:
class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while(fast!=null&&fast.next!=null)
{
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
}
大家也来试试吧:查找链表中间节点(电脑打开)
三、删除链表中等于给定值 val 的所有节点
思路演示:
代码展示:
class Solution {
public ListNode removeElements(ListNode head, int val) {
//排除空链表
if(head==null)
{
return null;
}
ListNode prev=head;
ListNode cur=prev.next;
while (cur!=null)
{
if (cur.val==val)
{
prev.next=cur.next;
}
else
{
//驱动双指针进行
prev=cur;
}
//驱动双指针进行
cur=cur.next;
}
//排除要删除的节点正好是头节点
if (head.val==val)
{
head=head.next;
}
return head;
}
}
大家也来试试吧:删除指定元素的所有节点
四.链表中倒数第k个结点
思路解析(双指针): 快慢指针从同意起点,快指针先走k-1步,此时加上fast本身。fast和slow相差k个节点,此时fast与slow同步一步一步向后走。当fast走到最后一个节点,slow恰好在倒数第k个节点
代码展示:
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast=head;
ListNode slow=head;
while(k-1>0)
{
fast=fast.next;
k--;
}
while(fast.next!=null)
{
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
大家也来试试吧:链表中倒数第k个结点
五.合并两个有序链表代码展示:
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//创建虚拟头节点
ListNode head=new ListNode(-1);
//定义node遍历新的头结点
ListNode node=head;
while(list1!=null&&list2!=null)
{
if(list1.val
node.next=list1;
list1=list1.next;
}
else
{
node.next=list2;
list2=list2.next;
}
node=node.next;
}
//如果list1是空链表,直接连接list2
if (list1== null) {
node.next = list2;
} else {
node.next = list1;
}
//返回虚拟节点下一个节点
return head.next;
}
}
大家也来试试吧:合并链表
六.以给定值x为基准将链表分割成两部分思路叙述:
新建两个链表 sml_dummy , big_dummy ,分别用于添加所有「节点值
若 head.val < x ,则将节点 head 添加至链表 sml_dummy 最后面; 若 head.val >= x ,则将节点 head 添加至链表 big_dummy 最后面;
遍历完成后,拼接 sml_dummy 和 big_dummy 链表。
最终返回头节点 sml_dummy.next 即可
lass Solution {
public ListNode partition(ListNode head, int x) {
ListNode smlDummy = new ListNode(0), bigDummy = new ListNode(0);
ListNode sml = smlDummy, big = bigDummy;
while (head != null) {
if (head.val < x) {
sml.next = head;
sml = sml.next;
} else {
big.next = head;
big = big.next;
}
head = head.next;
}
sml.next = bigDummy.next;
big.next = null;
return smlDummy.next;
}
}
大家也来试试吧:分割链表
七.删除链表重复节点 public Node deleteDuplication()
{
Node newHead=new Node(-1);
Node cur=this.head;
Node temp=newHead;
while (cur!=null)
{
if (cur.next!=null&&cur.date==cur.next.date)
{
while (cur.next!=null&&cur.date==cur.next.date) {
cur = cur.next;
}
cur=cur.next;
}
else
{
temp.next=cur;
temp=temp.next;
cur=cur.next;
}
}
temp.next=null;
return newHead.next;
八.判断回文链表
public boolean chkPalindrome()
{
if (this.head==null)
{
return false;
}
if (this.head.next==null)
{
return true;
}
Node fast=this.head;
Node slow=this.head;
while (fast!=null&&fast.next!=null)
{
fast=fast.next.next;
slow=slow.next;
}
Node cur = slow.next;
while (cur!=null)
{
Node curNext=cur.next;
cur.next=slow;
slow=cur;
cur=curNext;
}
while (this.head!=slow)
{
if (this.head.date!=slow.date)
{
return false;
}
if (this.head.next==slow)
{
return true;
}
this.head=this.head.next;
slow=slow.next;
}
return true;
大家也来试试吧回文链表
九.输入两个链表,找出它们的第一个公共结点public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
大家也来试试吧相交链表
十.判断链表是否有环public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while (fast!=null&&fast.next!=null)
{
fast=fast.next.next;
slow=slow.next;
if (fast==slow) {
return true;
}
}
return false;
}
}
大家也来试试吧环形链表
十一.返回链表开始入环的第一个节点public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while (fast!=null&&fast.next!=null)
{
fast=fast.next.next;
slow=slow.next;
if (fast==slow) {
break;
}
}
if (fast==null||fast.next==null)
{
return null;
}
slow=head;
while (fast!=slow)
{
fast=fast.next;
slow=slow.next;
}
return fast;
}
}
大家也来试试吧142. 环形链表 II



