- 两两交换链表中的节点
前后节点
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dom = new ListNode();
ListNode priv = null;
ListNode end = dom;
dom.next = head;
while (end.next!=null && end.next.next != null){
//翻转链表的前一个节点
ListNode old = end;
priv = end.next;
end = end.next.next;
//翻转链表的后一个节点 可能为null
ListNode next = end.next;
//翻转
old.next = end;
end.next = priv;
priv.next = next;
//已经翻转了
end = priv;
}
return dom.next;
}
19.删除链表的倒数第N个节点
快慢指针
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode end = null;
ListNode front = head;
n--;
while(n>0){
n--;
front = front.next;
}
if (front.next == null){
return head.next;
}
front = front.next;
end = head;
while (front.next != null){
front = front.next;
end = end.next;
}
end.next = end.next.next;
return head;
}
面试题 02.07. 链表相交
设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，
则有：
头节点 headA 到 node 前，共有 a−c 个节点；
头节点 headB 到 node 前，共有 b−c 个节点；
指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：
a+(b−c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：
b+(a−c)
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
142.环形链表II
设fast每次走两步，solw每次走一步；
设链表共有 a+b 个节点，其中 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点。设两指针分别走了 f，s 步,当两者相遇时则有
- fast 走的步数是slow步数的 2 倍，即 f=2s；（解析： fast 每轮走 2 步）
- fast 比 slow多走了 n 个环的长度，即 f=s+nb。
所以: f=2nb，s=nb.
此时将如果将慢指针前进a步即a+nb，则到达环的入口处
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
//
while (true) {
if (fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
