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

链表算法与数据结构实现

链表是一种常见的数据结构，广泛应用于编程中的各种场景。以下是一些链表相关的算法和实现，涵盖反转、排序、合并、判断回文以及树与链表转换等内容。

链表反转

反转链表是一项常见的链表操作，用于将链表的方向反转。以下是两种反转链表的实现方法：

public ListNode reverseList(ListNode head) {    if (head == null) {        return head;    }    // 设置新的节点    ListNode dumpy = new ListNode(-1);    dumpy.next = head;    ListNode pre = dumpy;    ListNode cur = head;    while (cur.next != null) {        ListNode future = cur.next;        cur.next = future.next;        future.next = pre.next;        pre.next = future;    }    return dumpy.next;}

public boolean isPalindrome(ListNode head) {    if (head == null) return true;    ListNode midNode = findMidNode(head);    ListNode secondHalfHead = reverseLinked(midNode.next);    ListNode curr1 = head;    ListNode curr2 = secondHalfHead;    boolean palindrome = true;    while (palindrome && curr2 != null) {        if (curr1.val != curr2.val) palindrome = false;        curr1 = curr1.next;        curr2 = curr2.next;    }    return palindrome;}private ListNode reverseLinked(ListNode head) {    ListNode cur = head;    ListNode prev = null;    while (cur != null) {        ListNode nextTemp = cur.next;        cur.next = prev;        prev = cur;        cur = nextTemp;    }    return prev;}private ListNode findMidNode(ListNode head) {    ListNode fast = head;    ListNode low = head;    while (fast.next != null && fast.next.next != null) {        fast = fast.next.next;        low = low.next;    }    return low;}

链表排序

链表排序可以通过快慢指针找到中间节点，然后递归地将左右子链表排序并合并。

public ListNode sortList(ListNode head) {    if (head == null || head.next == null) {        return head;    }    // 使用快慢指针    ListNode fast = head.next, slow = head;    while (fast != null && fast.next != null) {        slow = slow.next;        fast = fast.next.next;    }    ListNode tmp = slow.next;    slow.next = null;    // 递归拆分    ListNode left = sortList(head);    ListNode right = sortList(tmp);    // 合并链表    return mergeTwoLists(left, right);}public ListNode mergeTwoLists(ListNode l1, ListNode l2) {    // 创建一个新的链表    ListNode dummyHead = new ListNode(0);    ListNode cur = dummyHead;    while (l1 != null && l2 != null) {        if (l1.val < l2.val) {            cur.next = l1;            cur = cur.next;            l1 = l1.next;        } else {            cur.next = l2;            cur = cur.next;            l2 = l2.next;        }    }    // 任一为空，直接连接另一条链表    if (l1 == null) {        cur.next = l2;    } else {        cur.next = l1;    }    return dummyHead.next;}

链表反转部分节点

反转链表中从位置 m 到 n 的部分节点，可以通过逐步交换节点的指针来实现。

public ListNode reverseBetween(ListNode head, int m, int n) {    if (head == null) return head;    ListNode dumpy = new ListNode(-1);    dumpy.next = head;    ListNode pre = dumpy;    // 找到第 m 个节点    for (int i = 1; i < m; i++) {        pre = pre.next;    }    ListNode cur = pre.next;    for (int i = m; i < n; i++) {        ListNode future = cur.next;        cur.next = future.next;        future.next = pre.next;        pre.next = future;    }    return dumpy.next;}

二叉树转双向链表

将二叉树转换为双向链表的常见方法是通过深度优先搜索（DFS），并在访问左右子树时记录父节点的方向。

public class treeToDoublyList {    class TreeNode {        public int val;        public TreeNode left;        public TreeNode right;        public TreeNode() {}        public TreeNode(int _val) {            val = _val;        }        public TreeNode(int _val, TreeNode _left, TreeNode _right) {            val = _val;            left = _left;            right = _right;        }    }    private TreeNode ans;    private TreeNode removeNode;    private void dfs(TreeNode node, int flag) {        if (node != null) {            dfs(node.left, 0);        }        if (ans == null) {            ans = node;            removeNode = node;        } else {            if (flag == 0) {                removeNode.right = node;                node.left = removeNode;            } else {                removeNode.right = node;                node.left = removeNode;            }            removeNode = node;        }        if (node.right != null) {            dfs(node.right, 1);        }    }    public TreeNode treeToDoublyList(TreeNode root) {        if (root == null) {            return null;        }        ans = null;        removeNode = null;        dfs(root, 0);        return ans;    }}

判断链表是否为回文

判断链表是否为回文可以通过反转链表并与原链表比较，或者使用快慢指针法找到中间节点并比较两半的值。

public boolean isPalindrome(ListNode head) {    if (head == null) return true;    ListNode midNode = findMidNode(head);    ListNode secondHalfHead = reverseLinked(midNode.next);    ListNode curr1 = head;    ListNode curr2 = secondHalfHead;    boolean palindrome = true;    while (palindrome && curr2 != null) {        if (curr1.val != curr2.val) palindrome = false;        curr1 = curr1.next;        curr2 = curr2.next;    }    return palindrome;}public boolean isPalindrome1(ListNode head) {    // 使用快慢指针，慢指针在进行操作的时候，顺带的进行链表的翻转，在进行半个链表之间的比较    if (head == null) {        return true;    }    ListNode dummyNode = new ListNode(0);    dummyNode.next = head;    ListNode slow = dummyNode;    ListNode fast = dummyNode;    while (fast != null && fast.next != null) {        fast = fast.next.next;        // 链表翻转        ListNode temp = slow.next;        slow.next = prev;        prev = slow;        slow = temp;    }    // 比较两部分值    if (slow.val != slow.next.val) {        return false;    }    return true;}

重排链表

将链表节点按一定规则重新排列，可以利用栈来实现。

public void reorderList(ListNode head) {    if (head == null) {        return;    }    // 设置一个栈空间    Deque
   
     stack = new ArrayDeque<>();    ListNode curr = head;    // 将所有节点放入栈中    while (curr != null) {        stack.push(curr);        curr = curr.next;    }    curr = head;    ListNode stack_curr = new ListNode(Integer.MAX_VALUE);    while (curr.next != stack_curr.next) {        stack_curr = stack.poll();        stack_curr.next = curr.next;        curr.next = stack_curr;        curr = curr.next.next;    }    stack_curr.next = null;}
   

以上算法涵盖了链表的基本操作及其扩展应用，适用于不同场景的数据结构问题。

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