class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = head.next;
ListNode prev = null;
ListNode curr = head;
while (curr != null && curr.next != null) {
ListNode next = curr.next;//调换
curr.next = next.next;//调换
next.next = curr;//update
if (prev != null) {
prev.next = next;
}
prev = curr;
curr = curr.next;
}
return newHead;
}
}
19. class Solution {
// 主函数
public ListNode removeNthFromEnd(ListNode head, int n) {
// 虚拟头结点
ListNode dummy = new ListNode(-1);//dummy.next = 1 -> 2 -> 3 -> 4 -> 5
dummy.next = head;
// 删除倒数第 n 个，要先找倒数第 n + 1 个节点
ListNode x = findFromEnd(dummy, n + 1);//ListNode x = findFromEnd(dummy, n + 1) -->n+1 = 3
// 删掉倒数第 n 个节点
x.next = x.next.next; //(remove the node)
return dummy.next;
}
// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
ListNode p1 = head;
// p1 先走 k 步
for (int i = 0; i < k; i++) {
p1 = p1.next;//(move p1 forward)
//p1 = 2 -> 3 -> 4 -> 5
}
ListNode p2 = head;
// p1 和 p2 同时走 n - k 步
while (p1 != null) {
p2 = p2.next; //(move p2 forward)
p1 = p1.next;
//p2 = 1 -> 2
}
// p2 现在指向第 n - k 个节点
return p2;
}
}
class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA, p2 = headB;
while(p1 != p2){
if(p1 == null) p1 = headB;
else p1 = p1.next;
if(p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}
}
142.
class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast!= null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
break;
}
}
if(fast == null || fast.next ==null){
return null;
}
fast = head;
while(slow!= fast){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
