hot100之链表上
相交链表(160)先看代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA;
ListNode q = headB;
while (p != q){
p = p != null ? p.next : headB;
q = q != null ? q.next : headA;
}
return p;
}
}
[*]分析
将A的尾节点与B相连, B的尾节点与A相连
据图可知当(p, q)→(A, B指针)步频一致时, 会共同到达共有链表的初节点
反转链表(206)
先看代码
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
[*]分析
通过先置哨兵节点, 避免节点数量过少导致null pointer exception
回文链表(234)
先看代码
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null){
fast = fast.next;
slow = slow.next;
if (fast.next != null){
fast = fast.next;
}
}
ListNode rig = reverse(slow);
ListNode lef = head;
while (rig != null){
if (rig.val != lef.val){
return false;
}
rig = rig.next;
lef = lef.next;
}
return true;
}
private ListNode reverse(ListNode node){
ListNode prev = null;
while (node != null){
ListNode next = node.next;
node.next = prev;
prev = node;
node = next;
}
return prev;
}
}
[*]分析
通过快慢指针找到中心节点,反转中心节点后链表,取(lef, rig)→(链表头尾节点) 进行回文分析
环形链表(141)
先看代码
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null){
fast = fast.next;
slow = slow.next;
if (fast != null){
fast = fast.next;
}else return false;
if (fast == slow) return true;
}
return false;
}
}
[*]通过快慢指针, 快指针相对慢指针移动速度为1, 若有环, 必然追上慢指针
环形链表II(142)
先看代码
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
if (fast == null || fast.next == null) {
return null;
}
slow = head;
while (slow != fast){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
[*]分析
当快慢指针相遇时, 将慢指针置于head, 同步快慢指针步频, 再次相遇即为入口处
证明
f,s 为快慢指针移动的步数
a, b分别为为环外长度, 环内长度
由 f = 2s, f = s + n∗b
有 f = 2n∗b, s = n∗b
因 f + a = 2n∗b + a 此时快指针指向环形链表入口
取p = head, 有 (p+a)%(n∗b) == (f+a)%(n∗b) == a
p 和 f在入口相遇
合并两个有序链表(021)
先看代码
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode p1 =list1; ListNode p2 =list2; ListNode dummy = new ListNode(-1) ; ListNode res = dummy; while(p1!= null && p2!=null){ if ( p1.val
页:
[1]