前言

一、力扣24. 两两交换链表中的节点

迭代

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {ListNode node = new ListNode(-1, head);ListNode prev = node, cur = head;int temp;while(cur != null && cur.next != null){temp = cur.val;cur.val = cur.next.val;cur.next.val = temp;prev = cur.next;cur = prev.next;}return node.next;}
}

递归

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null){return head;}int temp;ListNode cur = head;temp = cur.val;cur.val = cur.next.val;cur.next.val = temp;ListNode node = swapPairs(cur.next.next);if(node == null){return cur;}return cur;}
}

二、力扣19. 删除链表的倒数第 N 个结点

直观法

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if(head == null){return head;}ListNode node = new ListNode(-1, head);ListNode pre = node, p = head;int i = 0, size = 0;while(p != null){size ++;p = p.next;}if(n > size){return head;}p = head;while(i < size-n){i ++;pre = p;p = p.next;}pre.next = p.next;return node.next;}
}

双指针法

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode node = new ListNode(-1, head);ListNode fast = node, slow = node;int i = 1;while(i <= n+1 && fast != null){i ++;fast = fast.next;}if(fast == null && i < n+1){return node.next;}while(fast != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return node.next;}
}

三、力扣面试题 02.07. 链表相交

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode longL = new ListNode(-1, headA);ListNode shortL = new ListNode(-1, headB);ListNode pa = headA, pb = headB;int lenA = 0, lenB = 0, diff = 0;while(pa != null){lenA ++;pa = pa.next;}while(pb != null){lenB ++;pb = pb.next;}if(lenA > lenB){diff = lenA - lenB;longL.next = headA;shortL.next = headB;}else{diff = lenB - lenA;longL.next = headB;shortL.next = headA;}pa = longL.next; pb = shortL.next;for(int i = 0; i < diff; i++){pa = pa.next;}while(pa != null && pb != null){if(pa == pb){return pa;}pa = pa.next;pb = pb.next;}return null;}
}

四、力扣142. 环形链表 II

因为快指针的速度是慢指针的两倍，所以，在进入环形之后，在快慢指针相遇之前，慢指针必然走不满一圈，设入环之前的节点数为x, 入环后到相遇节点之前为y个，相遇节点到入环处为z个，相遇时，快指针走过的节点数是慢指针的2倍，故有，2(x + y) = x + n(z + y) + y,，化简后为， x = n(z +y)-y，右边提取一个 y 得到，x = (n-1)(z+y) + z，此时的慢指针，一定会先走完z，然后就是n-1圈，就一直在进入点等待x

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fastNode = head, slowNode = head;while(fastNode != null && fastNode.next != null){fastNode = fastNode.next.next;slowNode = slowNode.next;if(fastNode == slowNode){ListNode index1 = head;ListNode index2 = slowNode;while(index1 != index2){index1 = index1.next;index2 = index2.next;}return index1;}}return null;}
}