LeetCode Hot 100 第11天
1. 160 相交链表
链接：题目链接
题解：
题解
时间复杂度O(n + m)：
- A链表长度为n，B链表长度为m。假设相交部分长度为x，那么未相交部分A链表就是n - x，B链表是m - x。
- 如果未相交部分A链表比B链表长，那么A链表头指针先走n - m步（n - x - m + x）。反之，B链表头指针先走m - n步。如果有公共节点，则相交且是第一个公共节点，反之，如果到了尾节点没相交，则说明不相交返回Null。
- 优化：如果默认两个链表一样长，就不用先去计算链表长度了。
那么 n + m == m + n，让两个链表头指针一起往后走，如果到达尾节点，切换另一个链表遍历。最终会到达第一个公共节点（注意：考虑没有公共节点的情况，那么最终同时到达Null节点，所以不需要特殊考虑）- 分析：虽然时间复杂度没变，都需要遍历两次链表，但是优化版本 考虑的分支明显更少，更简单。
代码：
优化版本：
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode currentNodeA = headA;ListNode currentNodeB = headB;while (currentNodeA != currentNodeB) {currentNodeA = currentNodeA == null ? headB : currentNodeA.next;currentNodeB = currentNodeB == null ? headA : currentNodeB.next;}return currentNodeA;}
}
未优化版本：
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 统计两个链表长度n, m 统计两个链表最后一个node// 判断最后一个Node是否相等，相等：有交点 不相等：没交点// 没交点：返回 null// 有交点：因为有交点，假设后面交点长度为x 那么没有交点的长度分别是 n - x、 m - x，让长的先走(n - m)步，然后两个链表一起往后走，直到遇到交点int n = 0, m = 0;ListNode aLastNode = null;ListNode bLastNode = null;ListNode currentNode = headA;while (currentNode != null) {aLastNode = currentNode;n++;currentNode = currentNode.next;}currentNode = headB;while (currentNode != null) {bLastNode = currentNode;m++;currentNode = currentNode.next;}if (aLastNode != bLastNode) {return null;}int advanceCount = Math.abs(n - m);if (n > m) {while (advanceCount > 0) {headA = headA.next;advanceCount--;}}if (m > n) {while (advanceCount > 0) {headB = headB.next;advanceCount--;}}while (headA != null && headB != null) {if (headA == headB) {return headA;}headA = headA.next;headB = headB.next;}return null;}
}
2. 206 反转链表
链接：题目链接
题解：
题解
时间复杂度O(n)：
- 前提：举例说明：a -> b -> c，如果一开始就扭转a、b之间指针的方向(a <- b c)，在没记录c节点的情况下，那么剩下的节点就没办法到达了。
- 递归：考虑递归到最后一对节点开始扭转，最后扭转a、b之间的方向。
（注意：需要让头结点的next置为Null，所以扭转完一对节点之后，需要让前节点的next置为Null）- 迭代：在扭转a、b节点前记录下c节点，以便于找到下一对需要扭转的b、c节点。
（注意：需要让头结点的next置为Null）
代码：
递归版：
class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode tailHead = reverseList(head.next);head.next.next = head;head.next = null;return tailHead;}
}
迭代版：
class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode preNode = head;ListNode currentNode = preNode.next;while (currentNode != null) {ListNode tempNode = currentNode.next;currentNode.next = preNode;preNode = currentNode;currentNode = tempNode;}head.next = null;return preNode;}
}
3. 234 回文链表
链接：题目链接
题解：
题解
时间复杂度O(n)：
- 判断是否为回文链表，肯定需要从中间往两边遍历 或者 从两边往中间遍历。那么肯定需要扭转一半链表的方向。
- 找到中间节点，再扭转中间节点 ~ 尾节点之间的顺序（参考上题），再从两端依次遍历是否相等既可。
- 找到中间节点：通过快慢指针找到中间节点（快指针一次走两步，慢指针走一步）。
代码：
class Solution {public boolean isPalindrome(ListNode head) {ListNode midNode = getMidNode(head);ListNode tailHead = reverse(midNode);while (tailHead != null && head.val == tailHead.val) {head = head.next;tailHead = tailHead.next;}return tailHead == null;}private ListNode getMidNode(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}private ListNode reverse(ListNode node) {if (node == null || node.next == null) {return node;}ListNode tailHead = reverse(node.next);node.next.next = node;node.next = null;return tailHead;}
}
4. 141 环形链表
链接：题目链接
题解：
题解
时间复杂度O(n)：
- 快慢指针（快指针一次走两步，慢指针走一步），相对论：在环里，慢指针没走，而快指针走一步，那么快指针一定会再次遇上慢指针。
- 如果快慢指针能相遇则有环，快指针走到尾则没环。
- 慢指针不需要考虑null情况，因为慢指针都是走快指针走过的路。
- 快指针需要考虑没环的情况，也就是为Null或者下个节点为Null的情况。
代码：
public class Solution {public boolean hasCycle(ListNode head) {ListNode low = head;ListNode fast = head;while (fast != null && fast.next != null) {fast = fast.next.next;low = low.next;if (fast == low) {break;}}return fast != null && fast.next != null;}
}
如果对你有帮助，辛苦点个赞，谢谢啦，朋友！！！