代码随想录day4| 24. 两两交换链表中的节点 、19.删除链表的倒数第N个节点 、面试题 02.07. 链表相交、 142.环形链表II、链表总结

24. 两两交换链表中的节点

思路

图文思路

步骤

• 创建虚拟头结点dumgHead，并创建cur节点指向虚拟头结点，用来操作后面两个节点的交换操作。
• 用while循环遍历链表，注意循环条件是，当cur的下一个节点为空或者下下一个节点为空时都不能进入循环：cur.next != null && cur.next.next != null。
• 循环中交换两个节点时需要保存cur.next.next.next和cur.next，用来交换节点。
• 最后将cur移动到下一对要交换的节点之前：cur = temp2，下次循环继续操作下两个节点。
• 推出循环后返回头结点dumgHead.next。

class Solution {public ListNode swapPairs(ListNode head) {ListNode dumgHead = new ListNode();dumgHead.next = head;ListNode cur = dumgHead;while(cur.next != null && cur.next.next != null){ListNode temp =  cur.next.next.next;ListNode temp2 = cur.next;cur.next = cur.next.next;temp2.next.next = temp2;temp2.next = temp;cur = temp2;}return dumgHead.next;}
}

19.删除链表的倒数第N个节点

思路

双指针的应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dumgHead = new ListNode();dumgHead.next = head;ListNode slow = dumgHead;ListNode fast = dumgHead;for(int i = 0 ; i < n ; i++){fast = fast.next;}while(fast.next != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dumgHead.next;}
}

面试题 02.07. 链表相交

步骤

• 定义两个指针分别指向两个链表的头结点（tempA、tempB）
• 用while循环让两个指针同时移动，当两个指针的下一个节点同时为null时下，循环结束（tempA.next != null || tempB.next != null）
• 两个节点的next没有同时指向null时，如果其中一个节点走到了尽头，则让他指向另一个链表的头结点。如果两个节点相遇，则说明这个节点为链表相交点，并返回
• 如果没有找到相交点，推出循环返回null
• 最后，在循环之前处理一下链表可能为空和两条链表都只有一个节点且相交的特殊情况。

图文思路

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode tempA = headA;ListNode tempB = headB;if(tempA == tempB){return tempA;}if(tempA == null || tempB == null){return null;}while(tempA.next != null || tempB.next != null){if(tempA.next == null){tempA = headB;}else{tempA = tempA.next;}if(tempB.next == null){tempB = headA;}else{tempB = tempB.next;}if(tempA == tempB){return tempA;}}return null;}
}

142.环形链表II

步骤

• 使用快慢指针（快指针每次走两步，慢指针每次走一步）找出相遇的点
• 用while循环遍历链表寻找是否有相遇的点。注意循环条件：fast != null && fast.next != null
• 若找到相遇的点，从头结点出发一个指针index1，从相遇节点 也出发一个指针index2，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点，返回该节点
• 若没有找到，则返回null

/*** 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 fast = head;ListNode slow = head;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;if(slow == fast){ListNode index1 = fast;ListNode index2 = head;while(index1 != index2){index1 = index1.next;index2 = index2.next;}return index2;}}return null;}
}

链表总结：

一般涉及到 增删改操作，用虚拟头结点都会方便很多， 如果只能查的话，用不用虚拟头结点都差不多。