Posts

题目 思路 如果链表无环，fast 会先走到 null，循环结束。 ...

环形链表2 题目 思路 用快慢指针判断是否有环 从相遇点定位入环点 把指针放在回头点，另外一个指针放在相遇点，两者每次都走一步，第一次相遇的就是入环点。 从头到入环点的距离为 a，入环点到相遇点沿着环走的距离为 b。 ...

K 个一组翻转链表 题目 思路 每轮探测是否有 K 个节点 翻转 head, tail 把翻转后的凭借回去。 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public ListNode reverseKGroup(ListNode head, int k) { if (head == null || k <= 1) { return head; } ListNode dummy = new ListNode(0, head); ListNode pre = dummy; while (true) { ListNode tail = pre; for (int i = 0; i < k; i ++) { tail = tail.next; if (tail == null) { return dummy.next; } } ListNode next = tail.next; ListNode groupHead = pre.next; reverse(groupHead, tail); pre.next = tail; groupHead.next = next; pre = groupHead; } } private void reverse(ListNode head, ListNode tail) { ListNode prev = null; ListNode cur = head; ListNode stop = tail.next; while(cur != stop) { ListNode nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; } } }

题目 思路 每次循环交换一对。 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; while (prev.next != null && prev.next.next != null) { ListNode a = prev.next; ListNode b = a.next; prev.next = b; a.next = b.next; b.next = a; prev = a; } return dummy.next; } }

题目 思路 等价于找到正数第 len - n 个节点的前一个节点。 ...

随机链表的复制 题目 思路 把复制节点插入到原链表中 每个旧节点紧跟着它的复制节点 复制 random 指针 拆分链表 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public Node copyRandomList(Node head) { if (head == null) { return null; } Node cur = head; while (cur != null) { Node copy = new Node(cur.val); copy.next = cur.next; cur.next = copy; cur = copy.next; } cur = head; while (cur != null) { Node copy = cur.next; copy.random = (cur.random == null) ? null : cur.random.next; cur = copy.next; } Node dummy = new Node(0); Node copyCur = dummy; cur = head; while (cur != null) { Node copy = cur.next; Node nextOld = copy.next; copyCur.next = copy; copyCur = copy; cur.next = nextOld; cur = nextOld; } return dummy.next; } }

合并两个有序链表 题目 思路 每次从两个链表头取出更小的节点接到新链表后面。 ...

反转链表 思路 把每个节点的指针反过来 迭代法，逐个拆链表，再接到新头部 递归法，先把后面的链表反转，再把当前节点接到尾巴 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode nxt = cur.next; cur.next = pre; pre = cur; cur = nxt; } return pre; } } 1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head } ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; } }

回文链表 思路 快慢指针找中点 反转左右 对比 Java 解法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } if (fast != null) { slow = slow.next; } ListNode second = reverse(slow); ListNode p1 = head, p2 = second; boolean ok = true; while (p2 != null) { if (p1.val != p2.val) { ok = false; break; } p1 = p1.next; p2 = p2.next; } return ok; } private ListNode reverse(ListNode head) { ListNode pre = null, cur = head; while (cur != null) { ListNode nxt = cur.next; cur.next = pre; pre = cur; cur = nxt; } return pre; } }

题目 思路 从右上角 (0, n - 1) 作为起点走楼梯，因为： ...