Posts

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

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

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

反转链表 思路 把每个节点的指针反过来 迭代法，逐个拆链表，再接到新头部 递归法，先把后面的链表反转，再把当前节点接到尾巴 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) 作为起点走楼梯，因为： ...

题目 思路 用两个指针 pA 指向 headA，pB 指向 headB，每次都走一步，当某个指针走到 null 时，让它跳到另外一个链表的头，直到相交。 ...

螺旋矩阵 思路 从外到内，按层遍历，一圈圈剥洋葱。 ...

题目 思路说明 前缀乘积 + 后缀乘积 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] ans = new int[n]; // 前缀乘积 ans[0] = 1; for (int i = 1; i < n; i++) { ans[i] = ans[i-1] * nums[i-1]; } // 后缀乘积 int suffix = 1; for (int i = n - 1; i >= 0; i--) { ans[i] = ans[i] * suffix; suffix *= nums[i]; } return ans; } } Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) ans = [1] * n for i in range(1, n): ans[i] = ans[i - 1] * nums[i - 1] suffix = 1 for i in range(n - 1, -1, -1): ans[i] *= suffix suffix *= nums[i] return ans JS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 var productExceptSelf = function(nums) { const n = nums.length; const ans = new Array(n); ans[0] = 1; for (let i = 1; i < n; i ++) { ans[i] = ans[i-1] * nums[i-1]; } let suffix = 1; for (let i = n - 1; i >= 0; i --) { ans[i] *= suffix; suffix *= nums[i]; } return ans; }; Go 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 func productExceptSelf(nums []int) []int { n := len(nums) ans := make([]int, n) ans[0] = 1 for i := 1; i < n; i ++ { ans[i] = ans[i-1] * nums[i -1] } suffix := 1 for i := n - 1; i >= 0; i-- { ans[i] *= suffix suffix *= nums[i] } return ans }

题目 思路 把子数组求和转换为前缀和差值计数。 ...