节选自：https://leetcode.cn/studyplan/top-100-liked/
链表反转
初始化 pre、cur 分别指向 null 和头节点。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head, pre = null;
while(cur != null) {
ListNode tmp = cur.next; // 暂存后继节点 cur.next
cur.next = pre; // 修改 next 引用指向
pre = cur; // pre 暂存 cur
cur = tmp; // cur 访问下一节点
}
return pre;
}
}相交链表
指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
如果 pA 到了末尾，则 pA = headB 继续遍历
- 如果 pB 到了末尾，则 pB = headA 继续遍历
- 比较长的链表指针指向较短链表head时，长度差就消除了
- 如此，只需要将最短链表遍历两次即可找到位置
有相交时A：a+c，B：b+c，且满足等式 a+c+b+c=b+c+a+c，因此他们走了 a+b+c 之后在 c 处相遇；
无相交时A：a+c1，B：b+c2。c1 与 c2 仅仅结点数量相同，因此 a+c1+b+c2=b+c2+a+c1，且a+c1+b=b+c2+a；但是接下来一个走c1一个走c2，距离 NULL 距离相同但是并非相交。
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;
}
}回文链表
可以直接用以下步骤完成本题：
- 复制链表值到数组列表中。
- 使用双指针法判断是否为回文。
但可以使用快慢指针+反转链表的方法实现空间复杂度 $O(1)$ ：
- 找到前半部分链表的尾节点。
- 反转后半部分链表。
- 判断是否回文。
- 恢复链表。
- 返回结果。
/**
* 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 boolean isPalindrome(ListNode head) {
if(head == null) return true;
// 找到前半部分的尾结点
ListNode fhalf = endOfFirstHalf(head);
ListNode sstart = reverseList(fhalf.next);
// 判断是否回文
ListNode p1 = head;
ListNode p2 = sstart;
boolean result = true;
while(result && p2 != null)
{
if(p1.val != p2.val) result = false;
p1 = p1.next; p2 = p2.next;
}
// 还原链表
fhalf.next = reverseList(sstart);
return result;
}
public ListNode reverseList(ListNode head)
{
ListNode pre = null; ListNode cur = head;
while(cur != null)
{
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
public ListNode endOfFirstHalf(ListNode head)
{
ListNode fast = head;
ListNode slow = head;
while(fast.next != null && fast.next.next != null)
{
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}合并两个有序链表
递归思想：
终止条件：当两个链表都为空时，表示我们对链表已合并完成。
如何递归：我们判断
l1和l2头结点哪个更小，然后较小结点的next指针指向其余结点的合并结果。（调用递归）
时间复杂度：$O(m+n)$。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
else if (l2 == null) {
return l1;
}
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}两数相加
/**
* 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 addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode cur = head;
int carry = 0;
while(l1 != null || l2 != null)
{
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
if(carry == 1) cur.next = new ListNode(carry);
return head.next;
}
}两两交换链表中的节点
递归确定的有以下三个条件：
- 返回值：交换完成的子链表
- 调用单元：设需要交换的两个点为 head 和 next，head 连接后面交换完成的子链表，next 连接 head，完成交换
- 终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
}排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
class ListNode {
int val;
ListNode next;
// 链表节点类的构造函数
ListNode(int x) {
val = x;
}
}
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 使用快慢指针找到链表中点
ListNode slow = head, fast = head, pre = null;
while (fast != null && fast.next != null) {
pre = slow; // pre指向slow的前一个节点，用于将链表从中点处断开
slow = slow.next; // 慢指针每次前进一步
fast = fast.next.next; // 快指针每次前进两步
}
pre.next = null; // 将链表从中点处断开
ListNode l1 = sortList(head); // 对前半部分链表排序
ListNode l2 = sortList(slow); // 对后半部分链表排序
return merge(l1, l2); // 合并两个有序链表
}
// 合并两个有序链表的方法
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0); // 创建一个虚拟头节点作为合并后链表的起始节点
ListNode cur = dummy; // cur指向当前合并后链表的最后一个节点
// 比较l1和l2中的元素，并依次将较小的元素加入到合并后链表中
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
// 当其中一个链表为空时，直接将另一个链表连接到合并后链表的末尾
if (l1 != null) {
cur.next = l1;
}
if (l2 != null) {
cur.next = l2;
}
return dummy.next; // 返回合并后链表的头节点（注意：虚拟头节点的下一个节点才是真正的头节点）
}
}
