代码随想录训练营｜Day4｜202，19，面试题02.07，142，总结

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]


Example 2:

Input: head = []
Output: []


Example 3:

Input: head = [1]
Output: [1]


Constraints:

• The number of nodes in the list is in the range [0, 100].


• 0 <= Node.val <= 100

Iteration

class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode prev = dummyNode;
while (prev.next != null && prev.next.next != null) {
ListNode temp = head.next.next; // 缓存 next
prev.next = head.next; // 将 prev 的 next 改为 head 的 next
head.next.next = head; // 将 head.next(prev.next) 的next，指向 head
head.next = temp; // 将head 的 next 接上缓存的temp
prev = head; // 步进1位
head = head.next; // 步进1位
}
return dummyNode.next;
}
}


Recursion

class Solution {
public ListNode swapPairs(ListNode head) {
// base case 退出提交
if(head == null || head.next == null) return head;
// 获取当前节点的下一个节点
ListNode next = head.next;
// 进行递归
ListNode newNode = swapPairs(next.next);
// 这里进行交换
next.next = head;
head.next = newNode;
return next;
}
}


Time Complexity：O(n)

Space Complexity：O(1)

For Future References

题目链接：https://leetcode.com/problems/swap-nodes-in-pairs/

文章讲解： https://programmercarl.com/0024.两两交换链表中的节点.html#_24-两两交换链表中的节点

视频讲解：https://www.bilibili.com/video/BV1YT411g7br/

19. Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]


Example 2:

Input: head = [1], n = 1
Output: []


Example 3:

Input: head = [1,2], n = 1
Output: [1]


Constraints:

• The number of nodes in the list is sz.


• 1 <= sz <= 30


• 0 <= Node.val <= 100


• 1 <= n <= sz

Follow up: Could you do this in one pass?

Get the length first

/**
* 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 dummy = new ListNode(0, head);
int length = getLength(head);
ListNode cur = dummy;
for(int i = 0; i cur = cur.next;
}
cur.next = cur.next.next;
return dummy.next;
}

public int getLength(ListNode head){
int length = 0;
while(head != null){
length++;
head = head.next;
}
return length;
}
}


w/o getting length (Two Pointers)

定义fast指针和slow指针，初始值为虚拟头结点

fast首先走n步

fast和slow同时移动，直到fast指向末尾

删除slow指向的下一个节点

/**
* 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 dummy = new ListNode(0, head);
ListNode slow = dummy;
ListNode fast = head;
for(int i = 0; i fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}


Time Complexity：O(n)

Space Complexity：O(1)

For Future References

题目链接：https://leetcode.com/problems/remove-nth-node-from-end-of-list/

文章讲解： https://programmercarl.com/0019.删除链表的倒数第N个节点.html

视频讲解：https://www.bilibili.com/video/BV1vW4y1U7Gf/

面试题 02.07. 链表相交

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

• intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.


• listA - The first linked list.


• listB - The second linked list.


• skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.


• skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

两个指针各自指向不同的head

两个指针同时开始走，如果到头就走去另一个linked list

两个指针相等的时候就是相交点

/**
* 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) {
if(headA == null || headB == null){
return null;
}
ListNode pointerA = headA;
ListNode pointerB = headB;
while(pointerA != pointerB){
pointerA = pointerA != null ? pointerA.next : headB;
pointerB = pointerB != null ? pointerB.next : headA;
}
return pointerA;
}
}


Time Complexity：O(n + m)

Space Complexity：O(1)

For Future References

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

文章讲解： https://programmercarl.com/面试题02.07.链表相交.html

142. Linked List Cycle II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.


Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.


Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.


Constraints:

• The number of the nodes in the list is in the range [0, 104].


• 105 <= Node.val <= 105


• pos is 1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。

此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：



那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。

从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

在相遇节点处，定义一个指针index1，在头结点处定一个指针index2

让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点

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


Time Complexity：O(n)

Space Complexity：O(1)

For Future References

题目链接：https://leetcode.com/problems/linked-list-cycle-ii/

文章讲解： https://programmercarl.com/0142.环形链表II.html#_142-环形链表ii

视频讲解：https://www.bilibili.com/video/BV1if4y1d7ob/

Summary

For Future References

文章讲解： https://programmercarl.com/链表总结篇.html#链表的理论基础