论坛 › 运维.售后 › 【Java-数据布局】Java 链外貌试题下 “末了一公里”：解决复杂链表题目的

飞不高 发表于 2025-2-13 17:21:53

【Java-数据布局】Java 链外貌试题下 “末了一公里”：解决复杂链表题目的

https://i-blog.csdnimg.cn/direct/b420b72947be43499b58f6148fb6d229.png
我的个人主页
我的专栏：Java-数据布局，希望能帮助到各人！！！点赞❤ 收藏❤
https://i-blog.csdnimg.cn/direct/0a43ce012e1f41c2829340d9ee39eaf1.gif#pic_center
https://i-blog.csdnimg.cn/direct/e3f1b17592a14d6da6bc318febdc9b46.gif#pic_center
   引言：
Java链表，看似简朴的链式布局，却蕴含着诸多有趣的特性与奥秘，等待我们去发掘。它就像一个神秘的宝藏迷宫，每一个特性都是隐蔽在迷宫深处的珍贵宝藏。链表的环，犹如迷宫中的循环通道，一旦进入，便大概陷入无尽的循环；链表节点的唯一性与重复性，仿佛迷宫中的岔路，有的道路独一无二，有的却似曾相识；而链表的长度变革，又犹如迷宫的动态扩展与收缩。在接下来的题目中，你将化身为勇敢的探险家，深入链表特性的迷宫，运用你的编程智慧，解开一个个谜题。通过检测链表的环、分析节点的重复性以及精准计算链表长度，你将徐徐揭开链表神秘的面纱，明白数据布局背后的奥妙逻辑。
6.编写代码，以给定值x为基准将链表分割成两部分，所有⼩于x的结点排在⼤于或等于x的结点之前—链表分割

   题目视图：
https://i-blog.csdnimg.cn/direct/46e6f4ed7b2542c0946cc6a5b56aaa98.png
题目详解代码：
// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
      next = null;
    }
}

public class PartitionList {
    public ListNode partition(ListNode pHead, int x) {
      // 创建两个虚拟头节点，分别用于存储小于 x 和大于等于 x 的节点
      ListNode smallDummy = new ListNode(0);
      ListNode largeDummy = new ListNode(0);
      // 分别指向两个新链表的当前节点
      ListNode smallTail = smallDummy;
      ListNode largeTail = largeDummy;

      // 遍历原链表
      ListNode current = pHead;
      while (current != null) {
            if (current.val < x) {
                // 如果当前节点的值小于 x，将其连接到 small 链表的尾部
                smallTail.next = current;
                smallTail = smallTail.next;
            } else {
                // 如果当前节点的值大于等于 x，将其连接到 large 链表的尾部
                largeTail.next = current;
                largeTail = largeTail.next;
            }
            // 移动到下一个节点
            current = current.next;
      }

      // 断开 large 链表的尾部，防止出现循环
      largeTail.next = null;
      // 将 small 链表和 large 链表连接起来
      smallTail.next = largeDummy.next;

      // 返回重新排列后的链表的头节点
      return smallDummy.next;
    }

    public static void main(String[] args) {
      // 创建测试链表 1 -> 4 -> 3 -> 2 -> 5 -> 2
      ListNode head = new ListNode(1);
      head.next = new ListNode(4);
      head.next.next = new ListNode(3);
      head.next.next.next = new ListNode(2);
      head.next.next.next.next = new ListNode(5);
      head.next.next.next.next.next = new ListNode(2);

      PartitionList solution = new PartitionList();
      int x = 3;
      // 调用 partition 方法进行重新排列
      ListNode newHead = solution.partition(head, x);

      // 打印重新排列后的链表
      ListNode current = newHead;
      while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
      }
    }
}
https://i-blog.csdnimg.cn/direct/b0eb31b537ba4dc38c8100bfe9dcd467.png
7.链表的回⽂布局。题目链接

   题目视图：https://i-blog.csdnimg.cn/direct/239a3b8d1aac4294810f9d19dcffaf8b.png
题目详解代码：
package Demo1_28;

/**
* Created with IntelliJ IDEA.
* Description:
* User：Lenovo
* Date:2025-01-28
* Time:20:04
*/
// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
      next = null;
    }
}

public class PalindromeLinkedList {
    public boolean isPalindrome(ListNode A) {
      if (A == null || A.next == null) {
            return true;
      }
      // 步骤 1：找到链表的中间节点
      ListNode slow = A;
      ListNode fast = A;
      while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
      }
      // 步骤 2：反转链表的后半部分
      ListNode secondHalf = reverseList(slow.next);
      // 步骤 3：比较链表的前半部分和反转后的后半部分
      ListNode p1 = A;
      ListNode p2 = secondHalf;
      boolean result = true;
      while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
      }
      // 步骤 4：恢复链表的原始结构
      slow.next = reverseList(secondHalf);
      return result;
    }

    // 反转链表的方法
    private ListNode reverseList(ListNode head) {
      ListNode prev = null;
      ListNode curr = head;
      while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
      }
      return prev;
    }

    public static void main(String[] args) {
      // 创建测试链表 1 -> 2 -> 2 -> 1
      ListNode head = new ListNode(1);
      head.next = new ListNode(2);
      head.next.next = new ListNode(2);
      head.next.next.next = new ListNode(1);

      PalindromeLinkedList solution = new PalindromeLinkedList();
      // 调用 isPalindrome 方法判断链表是否为回文结构
      boolean isPalindrome = solution.isPalindrome(head);
      System.out.println(isPalindrome);
    }
}
https://i-blog.csdnimg.cn/direct/153b4154c25a48e59f13b84eda71bffd.png
8.输⼊两个链表，找出它们的第⼀个公共结点。—题目链接

   题目视图：
https://i-blog.csdnimg.cn/direct/b25f2d36802b48459aa0ee36232e9a39.png
题目详解代码：
package Demo1_28;

/**
* Created with IntelliJ IDEA.
* Description:
* User：Lenovo
* Date:2025-01-28
* Time:20:08
*/
// 定义链表节点类
class ListNode {
    int val;
    ListNode next;

    // 构造函数，用于初始化节点的值
    ListNode(int x) {
      val = x;
      next = null;
    }
}

public class IntersectionOfTwoLinkedLists {
    // 查找两个链表相交的起始节点的方法
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      // 如果其中一个链表为空，直接返回 null
      if (headA == null || headB == null) {
            return null;
      }
      // 初始化两个指针分别指向两个链表的头节点
      ListNode pA = headA;
      ListNode pB = headB;
      // 当两个指针不相等时，继续循环
      while (pA != pB) {
            // 如果 pA 到达链表 A 的末尾，将其指向链表 B 的头节点
            pA = pA == null ? headB : pA.next;
            // 如果 pB 到达链表 B 的末尾，将其指向链表 A 的头节点
            pB = pB == null ? headA : pB.next;
      }
      // 返回相交节点，如果不相交则返回 null
      return pA;
    }

    public static void main(String[] args) {
      // 创建示例链表
      // 链表 A: 1 -> 2 -> 3 -> 6 -> 7
      ListNode headA = new ListNode(1);
      headA.next = new ListNode(2);
      headA.next.next = new ListNode(3);

      // 链表 B: 4 -> 5 -> 6 -> 7
      ListNode headB = new ListNode(4);
      headB.next = new ListNode(5);

      // 创建相交部分
      ListNode intersection = new ListNode(6);
      intersection.next = new ListNode(7);

      // 连接链表 A 和相交部分
      headA.next.next.next = intersection;
      // 连接链表 B 和相交部分
      headB.next.next = intersection;

      // 创建 IntersectionOfTwoLinkedLists 类的实例
      IntersectionOfTwoLinkedLists solution = new IntersectionOfTwoLinkedLists();
      // 调用 getIntersectionNode 方法查找相交节点
      ListNode result = solution.getIntersectionNode(headA, headB);
      if (result != null) {
            System.out.println("相交节点的值为: " + result.val);
      } else {
            System.out.println("两个链表不相交");
      }
    }
}

https://i-blog.csdnimg.cn/direct/40015806f3f64a97bac784ac8043b504.png
9.给你一个链表的头节点 head ，判断链表中是否有环。—题目链接

   题目视图：https://i-blog.csdnimg.cn/direct/cd0292d6554a48e591a3329a98ad973d.png
题目详解代码：
// 定义链表节点类
class ListNode {
    int val;
    ListNode next;

    // 构造函数，用于初始化节点的值
    ListNode(int x) {
      val = x;
      next = null;
    }
}

public class LinkedListCycle {
    // 判断链表是否有环的方法
    public boolean hasCycle(ListNode head) {
      // 如果链表为空或者只有一个节点，肯定没有环
      if (head == null || head.next == null) {
            return false;
      }
      // 慢指针，初始指向头节点，每次移动一步
      ListNode slow = head;
      // 快指针，初始指向头节点的下一个节点，每次移动两步
      ListNode fast = head.next;
      // 当慢指针和快指针不相等时，继续循环
      while (slow != fast) {
            // 如果快指针到达链表末尾或者快指针的下一个节点是末尾，说明没有环
            if (fast == null || fast.next == null) {
                return false;
            }
            // 慢指针移动一步
            slow = slow.next;
            // 快指针移动两步
            fast = fast.next.next;
      }
      // 如果跳出循环，说明慢指针和快指针相遇了，链表有环
      return true;
    }

    public static void main(String[] args) {
      // 创建有环链表 1 -> 2 -> 3 -> 4 -> 2（环从节点 2 开始）
      ListNode node1 = new ListNode(1);
      ListNode node2 = new ListNode(2);
      ListNode node3 = new ListNode(3);
      ListNode node4 = new ListNode(4);

      // 构建链表连接关系
      node1.next = node2;
      node2.next = node3;
      node3.next = node4;
      // 形成环
      node4.next = node2;

      // 创建 LinkedListCycle 类的实例
      LinkedListCycle solution = new LinkedListCycle();
      // 调用 hasCycle 方法判断链表是否有环
      boolean result = solution.hasCycle(node1);
      System.out.println("链表是否有环: " + result);

      // 创建无环链表 1 -> 2 -> 3 -> 4
      ListNode nodeA = new ListNode(1);
      ListNode nodeB = new ListNode(2);
      ListNode nodeC = new ListNode(3);
      ListNode nodeD = new ListNode(4);

      // 构建无环链表连接关系
      nodeA.next = nodeB;
      nodeB.next = nodeC;
      nodeC.next = nodeD;

      // 再次调用 hasCycle 方法判断无环链表是否有环
      result = solution.hasCycle(nodeA);
      System.out.println("链表是否有环: " + result);
    }
}
https://i-blog.csdnimg.cn/direct/fdd6310e431946b080a193bf5dfb6240.png
10.给定⼀个链表，返回链表开始⼊环的第⼀个节点。 如果链表⽆环，则返回 NULL

—题目链接
   题目视图：https://i-blog.csdnimg.cn/direct/cf103b382a2a42a8ac7c6e12647d7a9f.png
题目详解代码：
package Demo1_28;

/**
* Created with IntelliJ IDEA.
* Description:
* User：Lenovo
* Date:2025-01-28
* Time:20:15
*/
// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
      next = null;
    }
}

public class LinkedListCycleII {
    public ListNode detectCycle(ListNode head) {
      // 如果链表为空或只有一个节点，肯定没有环
      if (head == null || head.next == null) {
            return null;
      }
      // 慢指针，初始指向头节点，每次移动一步
      ListNode slow = head;
      // 快指针，初始指向头节点，每次移动两步
      ListNode fast = head;
      boolean hasCycle = false;

      // 寻找是否有环
      while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 快慢指针相遇，说明有环
            if (slow == fast) {
                hasCycle = true;
                break;
            }
      }

      // 如果没有环，返回 null
      if (!hasCycle) {
            return null;
      }

      // 慢指针重新指向头节点
      slow = head;
      // 快慢指针都以每次一步的速度移动，再次相遇的节点就是环的入口节点
      while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
      }
      return slow;
    }

    public static void main(String[] args) {
      // 创建有环链表 1 -> 2 -> 3 -> 4 -> 2（环从节点 2 开始）
      ListNode node1 = new ListNode(1);
      ListNode node2 = new ListNode(2);
      ListNode node3 = new ListNode(3);
      ListNode node4 = new ListNode(4);

      // 构建链表连接关系
      node1.next = node2;
      node2.next = node3;
      node3.next = node4;
      // 形成环
      node4.next = node2;

      // 创建 LinkedListCycleII 类的实例
      LinkedListCycleII solution = new LinkedListCycleII();
      // 调用 detectCycle 方法找到环的入口节点
      ListNode result = solution.detectCycle(node1);
      if (result != null) {
            System.out.println("环的入口节点的值为: " + result.val);
      } else {
            System.out.println("链表中没有环");
      }

      // 创建无环链表 1 -> 2 -> 3 -> 4
      ListNode nodeA = new ListNode(1);
      ListNode nodeB = new ListNode(2);
      ListNode nodeC = new ListNode(3);
      ListNode nodeD = new ListNode(4);

      // 构建无环链表连接关系
      nodeA.next = nodeB;
      nodeB.next = nodeC;
      nodeC.next = nodeD;

      // 再次调用 detectCycle 方法判断无环链表是否有环
      result = solution.detectCycle(nodeA);
      if (result != null) {
            System.out.println("环的入口节点的值为: " + result.val);
      } else {
            System.out.println("链表中没有环");
      }
    }
}

https://i-blog.csdnimg.cn/direct/35e5f332b5854b35966ddf52639cbb5f.png
所有的链表题目就分享到着了继续加油❤

查看完整版本: 【Java-数据布局】Java 链外貌试题下 “末了一公里”：解决复杂链表题目的