闻成 发表于 2025-6-14 12:40:00

hot100之链表上

相交链表(160)

先看代码
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      ListNode p = headA;
      ListNode q = headB;

      while (p != q){
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
      }
      return p;
    }
}

[*]分析
将A的尾节点与B相连, B的尾节点与A相连

据图可知当(p, q)→(A, B指针)步频一致时, 会共同到达共有链表的初节点
反转链表(206)

先看代码
class Solution {
    public ListNode reverseList(ListNode head) {
      ListNode prev = null;
      ListNode curr = head;
      while (curr != null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
      }
      return prev;
    }
}

[*]分析
通过先置哨兵节点, 避免节点数量过少导致null pointer exception
回文链表(234)

先看代码
class Solution {
    public boolean isPalindrome(ListNode head) {
      ListNode fast = head;
      ListNode slow = head;

      while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
            if (fast.next != null){
                fast = fast.next;
            }
      }
      ListNode rig = reverse(slow);
      ListNode lef = head;
      while (rig != null){
            if (rig.val != lef.val){
                return false;
            }
            rig = rig.next;
            lef = lef.next;
      }
      return true;

    }

    private ListNode reverse(ListNode node){
      ListNode prev = null;
      while (node != null){
            ListNode next = node.next;
            node.next = prev;
            prev = node;
            node = next;
      }
      return prev;
    }
}

[*]分析
通过快慢指针找到中心节点,反转中心节点后链表,取(lef, rig)→(链表头尾节点) 进行回文分析
环形链表(141)

先看代码
public class Solution {
    public boolean hasCycle(ListNode head) {
      ListNode fast = head;
      ListNode slow = head;

      while (fast != null){
            fast = fast.next;
            slow = slow.next;
            
            if (fast != null){
                fast = fast.next;
            }else return false;

            if (fast == slow) return true;
      }
      return false;
    }
}

[*]通过快慢指针, 快指针相对慢指针移动速度为1, 若有环, 必然追上慢指针
环形链表II(142)

先看代码
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 (slow != fast){
            fast = fast.next;
            slow = slow.next;
      }
      return slow;
    }
}

[*]分析
当快慢指针相遇时, 将慢指针置于head, 同步快慢指针步频, 再次相遇即为入口处
证明
f,s 为快慢指针移动的步数
a, b分别为为环外长度, 环内长度
由 f = 2s, f = s + n∗b
有 f = 2n∗b, s = n∗b
因 f + a = 2n∗b + a 此时快指针指向环形链表入口
取p = head, 有 (p+a)%(n∗b) == (f+a)%(n∗b) == a
p 和 f在入口相遇
合并两个有序链表(021)

先看代码
class Solution {    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {      ListNode p1 =list1;      ListNode p2 =list2;      ListNode dummy = new ListNode(-1) ;      ListNode res = dummy;      while(p1!= null && p2!=null){            if ( p1.val
页: [1]
查看完整版本: hot100之链表上