链表的第二部分。注意遇事不决多画图~

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]

要点

仔细画图模拟过程。可以使用虚拟头节点让事情简单点。
注意判断的时候，要 next 不是空，自身首先也要不是空。

代码

时间复杂度 O(N) 空间复杂度 O(1)

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode(val=0, next=head)
        curr = dummy_head
        prev = head 

        while prev is not None and prev.next is not None:
            curr = prev.next 
            # update value 
            tmp_val = prev.val 
            prev.val = curr.val 
            curr.val = tmp_val 
            # update prev pointer
            prev = curr.next 
        return head

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy_head = new ListNode(0, head);
        ListNode* curr = dummy_head;
        ListNode* prev = head;
        while (prev != NULL && prev->next != NULL) {
            curr = prev->next;
            // update value
            int tmp = prev->val;
            prev->val = curr->val;
            curr->val = tmp;
            // update prev pointer
            prev = curr->next; 
        }
        delete dummy_head;
        return head;
    }
};

19 删除链表的倒数第 N 个节点 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.

要点

双指针思路。快指针提前移动 n+1 步，之后让快慢指针同时向后移动。为什么是 n+1：前面的 n 步是留出来 “倒数第 n 个” 的，最后一步是保证快指针移动到末尾的时候，慢指针还在倒数第 n 个的前一个。
使用虚拟头节点。无论最后是不是空链表，都能返回虚拟头节点的下一个节点。

代码

时间复杂度 O(N) 空间复杂度 O(1)

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy_head = new ListNode(0, head);
        ListNode* fast = dummy_head;
        ListNode* slow = dummy_head;

        for (int i = 0; i <= n; i++) { // n+1 
            fast = fast->next;
        }

        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next;
        return dummy_head->next;
    }
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy_head = ListNode(val=0, next=head)
        fast = dummy_head
        slow = dummy_head

        for _ in range(n + 1):
            fast = fast.next
        
        while fast is not None:
            fast = fast.next 
            slow = slow.next 
        
        slow.next = slow.next.next 
        return dummy_head.next

面试题 02.07 链表相交 Intersection of Two Linked Lists LCCI

Given two (singly) linked lists, determine if the two lists intersect. Return the inter­ secting node. Note that the intersection is defined based on reference, not value. That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.

Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

要点

1. 借鉴上一题的思路，先让指针提前挪更长的那个比更短的那个链表长的步数，二者对齐后再一起往后移动，寻找是否相同
2. ListNode 节点相同需要用 nodeA == nodeB 来判断而非值

代码

时间复杂度 O(N) 空间复杂度 O(1)

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # calculate the length of A and B
        sizeA = sizeB = 0
        
        currA = headA
        while currA is not None:
            currA = currA.next 
            sizeA += 1
        
        currB = headB
        while currB is not None:
            currB = currB.next 
            sizeB += 1
        
        currA = headA
        currB = headB
        if sizeA > sizeB:
            diff = sizeA - sizeB 
            for _ in range(diff):
                currA = currA.next 
            while currA is not None:
                if currA == currB:
                    return currA
                else:
                    currA = currA.next
                    currB = currB.next 
            return None 
        else:
            diff = sizeB - sizeA
            for _ in range(diff):
                currB = currB.next 
            while currB is not None:
                if currA == currB:
                    return currB
                else:
                    currA = currA.next
                    currB = currB.next 
            return None

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *currA = headA;
        ListNode *currB = headB;
        int sizeA = 0;
        int sizeB = 0;

        while (currA != NULL) {
            currA = currA->next;
            sizeA++;
        }
        while (currB != NULL) {
            currB = currB->next;
            sizeB++;
        }

        currA = headA;
        currB = headB;

        if (sizeA - sizeB > 0) {
            int diff = sizeA - sizeB;
            for (int i = 0; i < diff; i++) {
                currA = currA->next;
            }
            while (currA != NULL) {
                if (currA == currB) {
                    return currA;
                } else {
                    currA = currA->next;
                    currB = currB->next;
                }
            }
        } else {
            int diff = sizeB - sizeA;
            for (int i = 0; i < diff; i++) {
                currB = currB->next;
            }
            while (currB != NULL) {
                if (currA == currB) {
                    return currB;
                } else {
                    currA = currA->next;
                    currB = currB->next;
                }
            }
        }
        return NULL;
    }
};

142 环形链表II Linked List Cycle II

要点

双指针解法。 快指针走两步，慢指针走一步。这个方法常用于比如：寻找尾部第K个节点、寻找环入口、寻找公共尾部入口等。

代码

时间复杂度 O(N) 空间复杂度 O(1)

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

        while fast != None and fast.next != None:
            slow = slow.next 
            fast = fast.next.next 

            if fast == slow:
                index1 = fast 
                index2 = head

                while index1 != index2:
                    index1 = index1.next
                    index2 = index2.next 
                return index1
        return None

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
     ListNode *fast = head;
     ListNode *slow = head;

     while (fast != NULL && fast->next != NULL) {
         fast = fast->next->next;
         slow = slow->next;

         if (fast == slow) { // first encounter
            ListNode *index1 = fast;
            ListNode *index2 = head;

            while (index1 != index2) {
                index1 = index1->next;
                index2 = index2->next;
            }
            return index2;
         }
     }
     return NULL;
    }
};

链表总结

虚拟头节点

链表的一大问题就是操作当前节点必须找前一个节点，头节点往往比较尴尬。在头节点需要单独处理的场合，使用虚拟头节点可以变得简洁。

链表的操作

• 获取链表的 第 index 个数值
• 在链表最前、最后插入节点
• 在链表第 index 节点前面插入节点
• 删除链表第 index 个节点的数值

反转链表

快慢指针 + 虚拟头节点。快指针指向头节点，慢指针指向虚拟头节点，二者一起往下走，遍历的同时让快指针反着指向慢指针，直到快指针为空。

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

使用双指针法，使用虚拟头节点。快指针提前走位 n+1 步，直到自己成为空。这样的 slow 指针的下一个 node 正好可以被删掉。

链表相交

首先一次遍历得到两个链表的长度。先挪动更长的一个链表的指针，直到剩余的数量一样长，再两个链表一起遍历指导节点本身相等。

环形链表

画图分析快慢指针何时相遇，及第一次相遇后，如何找到入口。快指针走两步，慢指针走一步。相遇后，再初始化两个指针一个从快指针的位置一个从头节点开始，二者一起走一步，相遇的位置即为入口。