【LeetCode、牛客】链表分割、链表的回文结构、160.相交链表

Hi~！这里是奋斗的明志，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
🌱🌱个人主页：奋斗的明志
🌱🌱所属专栏：数据结构

在这里插入图片描述

📚本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

在这里插入图片描述

链表面试题

一、链表分割
- 1. 题目
- 2. 方法一解析
- 3. 方法二解析
- 4. 方法一完整代码
- 5. 方法二完整代码
二、链表的回文结构
- 1. 了解链表的回文结构
- 2. 题目
- 3. 解析
- 4. 完整代码
三、相交链表
- 1. 题目
- 2. 解析
- 3. 完整代码

一、链表分割

链表分割

1. 题目

在这里插入图片描述

2. 方法一解析

初始化准备：

ListNode newHead1 = new ListNode(0);
ListNode tmp1 = newHead1;
ListNode newHead2 = new ListNode(0);
ListNode tmp2 = newHead2;

newHead1 和 tmp1 是用来存放小于 x 的节点的链表头和当前节点。
newHead2 和 tmp2 是用来存放大于等于 x 的节点的链表头和当前节点。
这里的 new ListNode(0) 是为了简化逻辑而创建的哨兵节点（dummy node），也就是虚拟节点不存储实际数据。

遍历原链表：

ListNode cur = pHead;
while (cur != null) {if (cur.val < x) {tmp1.next = cur;cur = cur.next;tmp1 = tmp1.next;} else {tmp2.next = cur;cur = cur.next;tmp2 = tmp2.next;}
}

使用 cur 作为遍历原链表 pHead 的指针。
如果 cur.val < x，将当前节点 cur 追加到 newHead1 的末尾，并更新 tmp1 指向最后一个节点。
如果 cur.val >= x，将当前节点 cur 追加到 newHead2 的末尾，并更新 tmp2 指向最后一个节点。
每次追加后，更新 cur 到下一个节点。

连接两个分区：

tmp2.next = null; // 将大于等于 x 的链表部分的末尾置空，避免形成环。
tmp1.next = newHead2.next; // 将小于 x 的链表部分的末尾连接到大于等于 x 的链表部分的头部。

返回结果：

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

返回 newHead1.next，即小于 x 的部分的头节点，因为 newHead1 的头节点是一个哨兵节点。

3. 方法二解析

在这里插入图片描述

初始化变量：

bs, be: 分别表示小于 x 的部分的头节点和尾节点。
as, ae: 分别表示大于等于 x 的部分的头节点和尾节点。

遍历链表：

使用 cur 指针遍历整个链表。
根据节点的值 cur.val 和给定的 x 进行判断，将节点加入对应的链表部分。

连接两部分：

如果 bs（小于 x 的部分）为空，则直接返回 as（大于等于 x 的部分）的头节点。否则，将 be（小于 x 的部分的尾节点）的next 指向 as 的头节点，连接两部分链表。
最后，将 ae 的 next 设置为 null，防止出现循环链表。

返回结果：

返回重新排列后的链表的头节点 bs。

4. 方法一完整代码

方法一：

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {if(pHead == null){return null;}if(pHead.next == null){return pHead;}ListNode newHead1 = new ListNode(0);ListNode tmp1 = newHead1;ListNode newHead2 = new ListNode(0);ListNode tmp2 = newHead2;ListNode cur = pHead;while(cur != null){if(cur.val < x){tmp1.next = cur;cur = cur.next;tmp1 = tmp1.next;}else{tmp2.next = cur;cur = cur.next;tmp2 = tmp2.next;}}tmp2.next = null;tmp1.next = newHead2.next;return newHead1.next;}
}

5. 方法二完整代码

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {if (pHead == null) {return null;}if (pHead.next == null) {return pHead;}ListNode cur = pHead;ListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;while (cur != null) {if (cur.val < x) {if (bs == null) {//说明一个节点都没有bs = cur;be = cur;} else {be.next = cur;be = be.next;}} else {if (as == null) {//说明一个节点都没有as = cur;ae = cur;} else {ae.next = cur;ae = ae.next;}}cur = cur.next;}if (bs == null) {return as;}be.next = as;if (as != null) {ae.next = null;}return bs;}
}

二、链表的回文结构

链表的回文结构

1. 了解链表的回文结构

链表的回文结构指的是链表从头到尾和从尾到头遍历得到的序列是相同的。
换句话说，正序和逆序遍历得到的节点值序列完全一致。

判断链表是否回文的方法
- 要判断一个链表是否为回文结构，可以采用以下方法之一：
- 利用额外空间：
- 将链表节点的值复制到数组中，然后利用数组的回文性质来判断。这种方法需要 O(n) 的额外空间，其中 n 是链表的长度。
- 利用快慢指针和翻转：
  
  使用快慢指针找到链表的中点。
  将后半部分链表进行翻转。
  然后同时从头部和中点开始遍历比较节点值，看是否相等。
  最后恢复链表原始结构（可选）。

2. 题目

在这里插入图片描述

3. 解析

空链表检查：

if (A == null) {return true;
}

如果输入的链表头节点 A 为空，直接返回 true，因为空链表被认为是回文的。

找到中间节点：
使用快慢指针法找到链表的中间节点：

在这里插入图片描述

ListNode fast = A;
ListNode slow = A;
while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;
}

快指针 fast 每次移动两步，慢指针 slow 每次移动一步，当快指针到达末尾时，慢指针恰好在链表的中间。

反转后半部分链表：

ListNode cur = slow.next;
while (cur != null) {ListNode curNext = cur.next;cur.next = slow;slow = cur;cur = curNext;
}

将从中间节点 slow.next 开始的链表部分进行反转，slow 成为反转后的头节点，最终 slow 指向反转后链表的尾节点。

比较前半部分和后半部分链表：
偶数情况见图：

while (slow != A) {if (slow.val != A.val) {return false;}if (A.next == slow) {return true;}A = A.next;slow = slow.next;
}

通过两个指针 A 和 slow 分别从链表头和中间向两端移动，比较节点值是否相等。如果任何时候值不相等，则返回 false，表示不是回文链表；如果 A 和 slow 指向同一个节点，说明链表比较完毕，返回 true，表示是回文链表。

总结:

这段代码通过快慢指针找到链表中间节点，反转后半部分链表，然后将前半部分和反转后的后半部分进行比较，来判断链表是否为回文链表。这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)，是一种比较高效的实现方式。

4. 完整代码

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/public class PalindromeList {public boolean chkPalindrome(ListNode A) {if(A == null){return true;}//1.找中间节点ListNode fast = A;ListNode slow = A;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}//cur代表要反转的链表ListNode cur = slow.next;while(cur != null){ListNode curNext = cur.next;cur.next = slow;slow = cur;cur = curNext;}//一个向前，一个向后while(slow != A){if(slow.val != A.val){return false;}if(A.next == slow){return true;}A = A.next;slow = slow.next;}return true;}
}

三、相交链表

160.相交链表

1. 题目

在这里插入图片描述

2. 解析

在这里插入图片描述

计算链表长度：
- 首先通过遍历两个链表分别计算它们的长度 lenA 和 lenB。
调整指针位置：
- 将 pl 指向较长的链表头，ps 指向较短的链表头，以便后续步骤中两个指针同时遍历，确保它们从同一起点开始。
移动指针到相同起点：
- 如果两个链表长度不同，先让较长链表的指针 pl 先走 len 步，使得 pl 和 ps 位于同一起点。
寻找交点：
- 同时移动 pl 和 ps 直到它们相遇（即找到交点）或者同时到达链表尾部（即没有交点）。
返回结果：
- 如果找到了交点，返回交点节点；否则返回 null。

这种方法的时间复杂度是 O(m + n)，其中 m 和 n 是两个链表的长度，因为需要分别遍历两个链表来计算长度和寻找交点。

3. 完整代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//分别求两个链表的长度int lenA = 0;int lenB = 0;ListNode pl = headA;//永远指向最长的链表ListNode ps = headB;//永远指向最短的链表while(pl != null){lenA++;pl = pl.next;}while(ps != null){lenB++;ps = ps.next;}pl = headA;ps = headB;int len = lenA - lenB;if(len < 0){//说明 pl 应该指向 headBpl = headB;ps = headA;len = lenB - lenA;}//保证 len 一定是正数//pl 指向最长的//ps 指向最短的while(len != 0){pl = pl.next;len--;}//pl ps 走到相遇节点的路程是一样的while(pl != null && pl != ps){pl = pl.next;ps = ps.next;}if(pl == ps && pl == null){return null;}return pl;}
}