【Java数据结构】经典链表OJ题——超详细做题笔记及心得

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

【Java数据结构】经典链表OJ题——超详细做题笔记及心得(每行代码都有注释嗷)

⭐1.反转链表

题目:
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
解题思路:
如下图,我们要实现的就是这样一个效果
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
要实现上图的效果,需要以下步骤:
①设置两个指针,cur 指向链表头节点,prev 指向空
暂存 cur 的后继节点,curNext = cur.next
③将 cur.next 反指向prev(一开始prev为空)
prev 指针后移,即将 prev 指向 cur
cur 指针后移 ,即将 cur 指向 2 中暂存的 curNext 节点
⑥循环: 第2 到 5 步,直到 cur 遍历完整个链表

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
   public ListNode reverseList(ListNode head) {
       if(head==null){
           System.out.println("链表为空");
       }
      //设置两个指针,cur 指向链表头节点,prev 指向空
       ListNode prev = null;
       ListNode cur = head;

       while(cur != null){
           ListNode curNext = cur.next;//暂存 cur 的后继节点,curNext = cur.next
           cur.next =prev;//将 cur.next 反指向prev(一开始prev为空)
           prev = cur;//prev 指针后移,即将 prev 指向 cur
           cur = curNext;//cur 指针后移 ,即将 cur 指向 2 中暂存的 curNext 节点
       }//循环: 第2 到 5 步,直到 cur 遍历完整个链表
       return prev;
   }
}

⭐2.给定一个带有头结点 head 的非空单链表,返回链表的中间结点

题目:
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
解题思路:
本题用的是双指针的方法
①分别设置一个快指针和一个慢指针
快指针每次走两步,慢指针每次走一步
③当快指针走到最后尾节点的时候,慢指针就走到了链表中间节点

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
   public ListNode middleNode(ListNode head) {
       ListNode fast = head;//快指针一开始指向头结点
       ListNode slow = head;//慢指针一开始也指向头结点
       while(fast!=null&&fast.next!=null){//由于要考虑偶数链表返回中间靠后的节点
       //所以要多设置一个fast.next!=null条件
           fast=fast.next.next;//快指针往后走两步
           slow=slow.next;//慢指针往后走一步
       }
       return slow;//返回慢指针
   }
}

⭐3.输入一个链表输出该链表中倒数第K个节点

题目:
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
解题思路:
这题和上题一样,采用双指针的办法,遍历链表一次就能达到目的
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
具体需要以下步骤:
①初始化: 前指针 former 、后指针 latter ,双指针都指向头节点 head​ 。
构建双指针距离: 前指针 former 先向前走 k-1 步(结束后,双指针 former 和 latter 间相距 k-1步)。
③双指针共同移动: 循环中,双指针 former 和 latter 每轮都向前走一步,直至 former 走到链表 尾节点 时跳出(跳出后, latter 与尾节点距离为 k-1步,即 latter 指向倒数第 k 个节点
④返回值: 返回 latter 即可。

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
   public ListNode getKthFromEnd(ListNode head, int k) {
       ListNode former = head;//设置一个先行节点,一开始指向头结点
       ListNode latter = head;//再设置一个后行节点,一开始指向头结点
       for(int i=1; i < k; i++){//构建双节点之间距离
           former = former.next;//
      }
       //构建距离完成之后,双节点同时向后走,直至先行节点到达尾节点处
       while(former.next!=null){//
           former = former.next;//
           latter = latter.next;//
       }
       return latter;//此时latter距离尾节点k-1步,也就是指向倒数第k个节点,直接返回latter即可
   }
}

⭐4.将两个有序链表合并为一个新的有序链表并返回

题目:
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
解题思路:
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
具体步骤如下
①设置傀儡节点,傀儡节点后边的节点组成的链表就是合并后的链表
②比较两个链表的每个节点,存入傀儡节点后的合并链表
③当有一条链已经遍历完成则将另一条链接到合并链表的尾部
④最后返回的是傀儡节点的下一个节点,这才是合并后的链表的头结点

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode newhead = new ListNode(-1);//创建一个虚拟傀儡节点,最后返回的是.next
       ListNode tmp =newhead;//创建局部引用,指向傀儡节点
       while (l1!=null && l2!=null) {//依次比较节点
           if (l1.val < l2.val) {//情况1
               tmp.next = l1;//将节点存入合并链表
               l1 = l1.next;//L2往后走一步
               tmp = tmp.next;//合并链表也要往后走一步好用于储存下一个比较结果
           } else {             //情况2
               tmp.next = l2;//将节点存入合并链表
               l2 = l2.next;//L2往后走一步
               tmp = tmp.next;//合并链表也要往后走一步好用于储存下一个比较结果
           }
       }
       if (l1==null){//当第一条链先走完
           tmp.next = l2;//将第二条链接到合并链表后
       }
       if (l2==null){//当第二条链先走完
           tmp.next = l1;//将第一条链接到合并链表后
       }
       return newhead.next;//最终返回傀儡节点的下一个节点,也就是合并链表的头结点
}

⭐5.分割链表

题目:
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
解题思路:
①本题用的双链表的方法,分别写一个A链表和B链表,A链表放值小于X的节点,B链表放值大于X的节点,依次遍历原链表就行了
不过要注意一个关键点,遍历结束后,我们将 L2 的next指针置空,这是因为当前节点复用的是原链表的节点,而其 指针可能指向一个小于 xx 的节点,我们需要切断这个引用
③最后将两个链表合成一个链表即可 (L1.next指向B.next就可以了)

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
   public ListNode partition(ListNode head, int x) {
       ListNode headA=new ListNode();//设置一个傀儡节点A,代表A链表
       ListNode headB=new ListNode();//再设置一个傀儡节点B,代表B表
       ListNode l1 = headA;//局部引用l1
       ListNode l2 = headB;//局部引用l2
       ListNode cur= head;//局部引用cur
       while(cur!=null){//遍历原链表
           if(cur.val<x){//小于X放A
               l1.next=cur;
               l1=l1.next;
           }else{        //大于X放B
               l2.next=cur;
               l2=l2.next;
           }
           cur=cur.next;//依次遍历
       }
       l2.next=null;//遍历结束后,我们将 l2 的next指针置空
       //这是因为当前节点复用的是原链表的节点,而其指针可能指向一个小于 xx 的节点
       //我们需要切断这个引用
       l1.next=headB.next;//链接两个链表,A的尾巴指向B的头
       return headA.next;//返回A的next,因为第一个节点其实是傀儡节点
       //第二个开始才是A链表的头结点
   }
}

⭐6.删除链表中重复节点(重复节点不保留)

题目:
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
解题思路:【Java数据结构】经典链表OJ题——超详细做题笔记及心得
主要思想就是遍历原链表,将不重复的节点提取出来放到一个新的链表里
①遍历原链表(利用临时变量cur代替头结点)
②创建一个新头结点,代表一个新链表
判断当前节点与下一个节点是否相同,如果相同则cur往后走一步,不同则将此节点存入新节点
④返回新头结点的下一节点(新头结点其实是傀儡节点,新链表其实是从第二个节点开始的)

public ListNode deleteDuplicates(ListNode head) {
       ListNode cur = head;//设置临时变量代替头结点遍历原链表
       ListNode newHead = new ListNode(-1);//创建一个新头结点代表一个新的链表
       ListNode tmp = newHead;//设置临时变量代替新链表的头结点
       while (cur != null) {//设置终止条件
           if (cur.next != null && cur.val == cur.next.val) {
           //判断当前节点值是否等于下一个节点
           //前提是下一个节点不为null,不然会有空指针导致访问异常
               while (cur.next != null && cur.val == cur.next.val) {
               //这里还需要考虑到有两个以上重复的节点怎么处理
               //所以还需要一个while来跳过重复节点
                   cur = cur.next;
               }
               cur = cur.next;//往后多走一步,因为题目要求不需要保留重复节点
           } else {//不满足等值条件的点,直接跳过,往后遍历即可
               tmp.next = cur;
               tmp = tmp.next;
               cur = cur.next;
         }
       }
       //防止最后一个节点值也是重复的
       tmp.next = null;//因为cur是原链表的引用,后边还会指向原链表中的节点
       //所以要置空,只保留当时cur指向的那个节点
       return newHead.next;
   }

⭐7.判断链表是否是回文结构

题目:
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
解题思路:
本题首先得了解什么是回文结构,回文结构就是正着读反着读都一样的链表
①快慢指针法找中间节点
②后半段链表反转
判断两端链表是否相同
④注意考虑链表为偶数的情况

public boolean isPalindrome(ListNode head) {
       ListNode fast = head;
       ListNode latter = head;

       //找中间点
       while(fast!=null&&fast.next!=null){//经典的快慢指针法找中间点,就不多bb了
           fast=fast.next.next;
           latter=latter.next;
       }
       //后半段反转
       ListNode cur=latter.next;
       while(cur!=null){//经典的反转链表,也不多BB了,具体方法请看第一题
           ListNode curNext=cur.next;//设置暂存点
           cur.next=latter;
           latter=cur;
           cur = curNext;
       }

       //判断两段链表是否相同
       while(head!=latter){//head从头往后走,latter从后往前走,直到相遇
           if(head.val==latter.val){//判断两段链表值是否相等
              if (head.next == latter) {//考虑链表为偶数的情况
                    return true;//偶数链表的情况头结点下一个节点就是latter的时候直接返回true
               }
           }
           else{
               return false;
           }
           latter=latter.next;//latter依次遍历
           head=head.next;//head依次遍历
       }
       return true;//能跳出循环说明,链表符合回文结构,返回true
   }

⭐8.找出两个链表的第一个公共节点

题目:
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
解题思路:这里说一种很6P的解法,是leetcode上看到的一个题解
直接将两条路分别拼接在对方末尾,这样两条路便一样长,再从这两条新的路起始点往后比较即可,如下图 节点相同地方一句圈起来,两条链表记住,公共节点指的就是公用一个节点,不是值相同,所以要对比的是地址蓝色连接代表链表结束换路【Java数据结构】经典链表OJ题——超详细做题笔记及心得
①设置两个临时节点节点,分别指向A链表头结点和B链表头结点

②只要这两个临时节点不指向同一个地址,就说明还没走到第一个公共节点
当临时节点走到一条链表的尾节点时(p1/p2.nextnull)就走另外一条链
④啥时候p1等于p2了,即
p1和p2指向同一个地址了==,这个地址就是第一个公共节点的地址,返回其即可

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       ListNode p1 = headA, p2 = headB;//设置两个临时节点节点
                                       //分别指向A链表头结点和B链表头结点
        while(p1 != p2){
            p1 = p1 == null ? headB : p1.next;//p1依次往后遍历,走到尾节点了就走另一条链表
            p2 = p2 == null ? headA : p2.next;//p2依次往后遍历,走到尾节点了就走另一条链表
        }
        return p1;//跳出循环了说明找到公共节点了
   }

⭐9.判断链表是否有环

题目:
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
解题思路:
找环其实就是一个追击问题,依旧采取双指针的方法,设置一个快指针一个慢指针,快指针每次走两步慢指针每次走一步如果链表有环,快指针和慢指针终究会相遇,因为跑的快的人最终肯定会超跑得慢的人一圈,当他们相遇的时候刚好超了一圈
①设置一个快指针,一个慢指针
②两个指针都指向头结点
快指针每次走两步,慢指针每次走一步
④如果有环,两个指针一定会在某一时刻相遇,否则无环

public boolean hasCycle(ListNode head) {
       ListNode fast = head;//设置快指针,指向头结点
       ListNode slow = head;//设置慢指针,指向头结点
       ListNode cur = head;//设置临时变量代替头结点,用于遍历链表

       while(fast!=null&&fast.next!=null ){
           fast=fast.next.next;//快指针每次走两步
           slow=slow.next;//慢指针每次走一步
           if(fast==slow)//快慢指针相遇
           return true;//说明有环
       }
       return false;//快慢指针没相遇说明无环
   }

⭐10.返回链表开始入环的第一个节点

题目:
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
解题思路:
我们使用两个指针,fast 与 slow。它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而fast 指针向后移动两个位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇
如下图所示,设链表中环外部分的长度为 a。slow 指针进入环后,又走了 b 的距离与 fast 相遇。此时,fast 指针已经走完了环的 n 圈,因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc
【Java数据结构】经典链表OJ题——超详细做题笔记及心得根据题意,任意时刻,fast 指针走过的距离都为slow 指针的 2 倍。因此,我们有
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
有了 a=c+(n-1)(b+c)的等量关系,我们会发现:从相遇点到入环点的距离加上 n-1圈的环长,恰好等于从链表头部到入环点的距离。
因此,当发现 slow 与 fast 相遇时,我们再额外使用一个指针 tmp它指向链表头部随后,它和 slow 每次向后移动一个位置。最终,它们会在入环点相遇。

解题步骤:
①利用快慢指针方法找相遇点
②找到相遇点之后,设置临时变量tmp代替头结点,tmp和slow同时移动,直至相遇
相遇点即为环的呃入口

public ListNode detectCycle(ListNode head) {
           if(head==null||head.next==null)//先判断链表不为空或者链表有至少两个元素
           return null;
       //利用快慢指针,找到快慢指针的相遇点
       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==slow){
           ListNode tmp = head;//临时变量代替头结点
           while(tmp!=slow){//tmp和slow同时移动
               slow = slow.next;
               tmp = tmp.next;
           }
           return tmp;//tmp和slow相遇的节点就是环的入口点
       }
       return null;
   }

上一篇:OJ---百钱买百鸡问题


下一篇:SWUST OJ 281: 逃跑的蠕虫