本文共 4607 字，大约阅读时间需要 15 分钟。

链表操作技术总结

链表反转

链表反转是一项基础的链表操作，常见于解决链表倒序问题。以下是反转链表的主要思路和实现方法：

public ListNode reverseList(ListNode head) {    if (head == null || head.next == null) return head;    ListNode cur = head, next = head.next;    cur.next = null;    while (next != null) {        ListNode temp = next.next;        next.next = cur;        cur = next;        next = temp;    }    return cur;}

回文链表判断

判断一个链表是否为回文链表，可以采用双向链表的方法：

public boolean isPalindrome(ListNode head) {    Deque
   
     deque = new LinkedList<>();    while (head != null) {        deque.addLast(head.val);        head = head.next;    }    int sizeHalf = deque.size() / 2;    for (int i = 0; i < sizeHalf; i++) {        if (deque.pollFirst() != deque.pollLast()) return false;    }    return true;}
   

快慢指针法

快慢指针是一种常见的链表操作技巧，广泛应用于查找链表中特定节点和判断回文等问题。以下是典型应用方法：

public boolean isPalindrome(ListNode head) {    if (head == null || head.next == null) return true;    ListNode slow = head, fast = head;    ListNode prepre = null, pre = head;    while (fast != null && fast.next != null) {        slow = slow.next;        fast = fast.next.next;        // 反转指针        ListNode temp = pre.next;        pre.next = prepre;        prepre = pre;        pre = temp;    }    // 处理奇数长度的情况    if (fast != null) slow = slow.next;    // 比较是否为回文    while (prepre != null) {        if (prepre.val != slow.val) return false;        prepre = prepre.next;        slow = slow.next;    }    return true;}

链表倒数第k个节点

找到链表倒数第k个节点，可采用快慢指针方法：

public ListNode getKthFromEnd(ListNode head, int k) {    if (k <= 0) return null;    // 快指针先走k步    ListNode fast = head;    for (int i = 0; i < k; i++) {        if (fast == null) return fast;        fast = fast.next;    }    // 慢指针和快指针一起走    ListNode slow = head;    while (fast != null) {        fast = fast.next;        slow = slow.next;    }    return slow;}

链表删除节点

删除链表中的一个节点，需要注意以下几点：

public void deleteNode(ListNode node) {    // 当node是头节点    if (node.prev == null) {        return node.next;    }    // 调整前一个节点的指针    node.prev.next = node.next;    // 当node是尾节点    if (node.next == null) {        return node.prev;    }    // 调整当前节点的指针    node.next = node.next.next;}

两个链表的第一个公共节点

找到两个链表的第一个公共节点，可以采用以下方法：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {    if (headA == null || headB == null) return null;    // 保存两个链表的头节点    ListNode hA = headA, hB = headB;    while (headA != null || headB != null) {        // 检查是否有公共节点        if (headA == headB) return headA;        // 调整指针        headA = headA != null ? headA.next : hB;        headB = headB != null ? headB.next : hA;    }    return null;}

复杂链表的复制

复制一个带有随机指针的链表，可以采用哈希表的方法：

public Node copyRandomList(Node head) {    Map
   
     map = new HashMap<>();    Node cur = head;    while (cur != null) {        map.put(cur, new Node(cur.val));        cur = cur.next;    }    cur = head;    while (cur != null) {        Node curNew = map.get(cur);        if (cur.next != null) {            curNew.next = map.get(cur.next);        }        if (cur.random != null) {            curNew.random = map.get(cur.random);        }        cur = cur.next;    }    return map.get(head);}
   

二叉搜索树转双向链表

将二叉搜索树转换为双向链表，可以采用以下方法：

public Node treeToDoublyList(Node root) {    List
   
     list = new ArrayList<>();    inorder(root, list);    // 生成双向链表    for (int i = 0; i < list.size() - 1; i++) {        list.get(i).right = list.get(i + 1);        list.get(i + 1).left = list.get(i);    }    // 头尾连接    list.get(0).left = list.get(list.size() - 1);    list.get(list.size() - 1).right = list.get(0);    return list.get(0);}public void inorder(Node root, List
    
      list) {    if (root == null) return;    inorder(root.left, list);    if (root.left != null) {        root.left.right = root;    }    root.left = root;    root = root.right;    list.add(root);}
    
   

以上是对多个链表操作问题的详细解答和优化，涵盖了反转、判断回文、删除节点、找到公共节点等常见操作。每个问题都提供了优化后的代码实现和详细的步骤说明，确保内容清晰易懂。

转载地址：http://iqqn.baihongyu.com/