1.回文链表（234-中）
问题描述：判断一个链表是否回文，要求： O(n) 时间复杂度和 O(1) 空间复杂度
案例：
输入: 1->2 输出: false
思路：最简单的是使用栈，全部元素入栈，出栈比较一半元素，见代码。
如果不使用额外空间。思路如下：
- 快慢指针找到链表的中间位置（左中点）；
- 反转链表的前半部分；
- 依次比较判断回文。slow节点记录后半部分，pre记录反转后的前半部分
注意：这里我们采用一边反转链表，一边找中间那位置。slow节点相当于记录了反转链表的next节点。
代码:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { // 利用栈（链表入栈，然后比较一半，ps：比较的是节点值） public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } Deque<ListNode> stack = new LinkedList<>(); int len = 0; ListNode cur = head; while (cur != null) { stack.push(cur); len++; cur = cur.next; } len >>= 1; while (len-- >= 0) { if (stack.pop().val != head.val) { return false; } head = head.next; } return true; } // 快慢指针找中点（左中点） + 反转前一半链表 public boolean isPalindrome(ListNode head) { ListNode slow = head, fast = head; ListNode pre = null, cur = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; cur.next = pre; pre = cur; cur = slow; } // 链表长度为奇数时 if (fast != null) { slow = slow.next; } while (slow != null) { if (pre.val != slow.val) { return false; } pre = pre.next; slow = slow.next; } return true; } }
2.复制带随机指针的链表（138-中）
问题描述：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。返回复制链表的头节点。你的代码 只 接受原链表的头节点 head 作为传入参数。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
- val：一个表示 Node.val 的整数。
- random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
案例：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
思路：解法1：可以直接使用哈希表进行映射<原节点，原节点的副本>，再通过映射去创建（复制）新节点和新节点的next和random指针（注意空指针）。
解法2比较巧妙：对于每个链表的next节点创建一个副本，连接副本的random指针，分离两个链表，注意两点：
- 虚拟头节点的技巧
- 恢复原链表（一起连接两个链表的next节点）
代码:
/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { // hash映射<原节点，原节点的副本> public Node copyRandomList(Node head) { if (head == null) { return null; } HashMap<Node, Node> map = new HashMap<>(); Node p = head; while (p != null) { Node copyNode = new Node(p.val); map.put(p, copyNode); p = p.next; } p = head; while (p != null) { Node newNode = map.get(p); if (p.random != null) { newNode.random = map.get(p.random); } if (p.next != null) { newNode.next = map.get(p.next); } p = p.next; } return map.get(head); } // 原链表创建副本，然后分离 public Node copyRandomList(Node head) { if (head == null) { return null; } Node p = head; while (p != null) { Node newNode = new Node(p.val); newNode.next = p.next; p.next = newNode; p = newNode.next; } p = head; while (p != null) { if (p.random != null) { p.next.random = p.random.next; } p = p.next.next; } p = head; Node dummyHead = new Node(-1); Node cur = dummyHead; while (p != null) { cur.next = p.next; cur = cur.next; // ps:原链表恢复 p.next = cur.next; p = p.next; } return dummyHead.next; } }
3.链表的中间节点（876-易）
题目描述：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例：
输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
思路：快慢指针解法，注意偶数节点情况，这里提供返回第一和第二个中间节点的代码。不同点：快指针的初始位置！
代码：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { // 返回第一个中间节点 public ListNode middleNode(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } // 返回第二个中间节点 public ListNode middleNode(ListNode head) { ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } }
4.有序链表转二叉搜索树（109-中）
题目描述：给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例：
给定的有序链表： [-10, -3, 0, 5, 9], 一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5
思路：给定条件：链表升序！下面都是使用分治的思想：
- 常规解法：寻找链表的中间节点（快慢指针），注意：要断链表
- 终止条件：没有元素和只有一个元素（创建二叉树节点）
- 断链表，创建根节点，递归构建左右子树
- 另解：先递归的构建树（需要知道构建树的左右边界），当遍历到该位置再填值。
代码：
/** * 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; } * } */ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { // 找中间节点（的前一个节点） + 分治思想 public TreeNode sortedListToBST(ListNode head) { if (head == null) { return null; } if (head.next == null) { return new TreeNode(head.val); } ListNode pre = preMid(head); ListNode mid = pre.next; // 断链表 pre.next = null; TreeNode root = new TreeNode(mid.val); root.left = sortedListToBST(head); root.right = sortedListToBST(mid.next); return root; } private ListNode preMid(ListNode head) { ListNode slow = head, fast = head; ListNode pre = null; while (fast != null && fast.next != null) { pre = slow; slow = slow.next; fast = fast.next.next; } return pre; } // 先建树（分治），后填值！ private ListNode globalNode; public TreeNode sortedListToBST(ListNode head) { if (head == null) { return null; } ListNode cur = head; int len = 0; while (cur != null) { len++; cur = cur.next; } globalNode = head; return buildTree(0, len - 1); } private TreeNode buildTree(int left, int right) { if (left > right) { return null; } int mid = left + (right - left) / 2; TreeNode root = new TreeNode(); root.left = buildTree(left, mid - 1); root.val = globalNode.val; globalNode = globalNode.next; root.right = buildTree(mid + 1, right); return root; } }
