LeetCode热题100(25.10.6)

一：环形链表2️⃣

1. 哈希表

这道题的思路和环形链表的方法一相同

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> hashTable;
        while (head != nullptr)
        {
            if (hashTable.count(head)) return head;
            hashTable.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> hashTable = new HashSet<ListNode>();
        while (head != null)
        {
            if (hashTable.contains(head)) return head;			
            hashTable.add(head);
            head = head.next;
        }
        return null;
    }
}

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        hashTable = set()
        while head:
            if head in hashTable:
                return head
            hashTable.add(head)
            head = head.next
        return None

2. 快慢指针

这道题的思路和环形链表的方法二相同，如果有环相遇点一定在环中，且快指针比慢指针多n圈，进入环之后快指针比慢指针多一圈

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) return nullptr;
        ListNode* fastNode = head;       
        ListNode* slowNode = head;
        while (fastNode != nullptr)
        {
            if (fastNode == nullptr || fastNode->next == nullptr) return nullptr;
            slowNode = slowNode->next;
            fastNode = fastNode->next->next;
            if (fastNode == slowNode)
            {
                ListNode* cur = head;
                while ( cur != slowNode) 
                {
                    cur = cur->next;
                    slowNode = slowNode->next;
                }
                return cur;
            }
        }
        return nullptr;
    }
};

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode fastNode = head;       
        ListNode slowNode = head;
        while (fastNode != null)
        {
            if (fastNode == null || fastNode.next == null) return null;
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
            if (fastNode == slowNode)
            {
                ListNode cur = head;
                while ( cur != slowNode) 
                {
                    cur = cur.next;
                    slowNode = slowNode.next;
                }
                return cur;
            }
        }
        return null;
    }
}

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if (head == None or head.next == None): return None
        fastNode = head       
        slowNode = head
        while (fastNode != None):
            if (fastNode == None or fastNode.next == None): return None
            slowNode = slowNode.next
            fastNode = fastNode.next.next
            if (fastNode == slowNode):
                cur = head
                while ( cur != slowNode): 
                    cur = cur.next
                    slowNode = slowNode.next
                return cur
        return None

二：两数相加

1. 模拟

直接对对应节点的数字进行相加，难点在于处理进位和非对齐的场景

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode* head = nullptr;
        ListNode* cur = nullptr;
        while (l1 != nullptr || l2 != nullptr)
        {
            int num1= l1 ? l1->val : 0;
            int num2= l2 ? l2->val : 0;
            int sum= num1 + num2 + carry;
            if (head == nullptr)
                cur = head = new ListNode(sum % 10);
            else
                cur = cur->next = new ListNode(sum % 10);
            carry = sum / 10;
            if (l1 != nullptr) l1 = l1->next;
            if (l2 != nullptr) l2 = l2->next;
        }
        if (carry != 0) cur->next = new ListNode(carry);
        return head;
    }
};

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode head = null;
        ListNode cur = null;
        while (l1 != null || l2 != null)
        {
            int num1= l1 != null ? l1.val : 0;
            int num2= l2 != null ? l2.val : 0;
            int sum= num1 + num2 + carry;
            if (head == null)
                cur = head = new ListNode(sum % 10);
            else
                cur = cur.next = new ListNode(sum % 10);
            carry = sum / 10;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry != 0) cur.next = new ListNode(carry);
        return head;
    }
}

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        carry = 0
        head = None
        cur = None
        while (l1 != None or l2 != None):
            num1 = l1.val if l1 else 0
            num2 = l2.val if l2 else 0
            sum= num1 + num2 + carry
            if (head == None):
                head = ListNode(sum % 10)
                cur = head
            else:
                cur.next = ListNode(sum % 10)
                cur = cur.next
            carry = sum // 10
            if (l1 != None): l1 = l1.next
            if (l2 != None): l2 = l2.next
        if (carry != 0): cur.next = ListNode(carry)
        return head

三：删除链表的倒数第 N 个结点

1. 计算链表长度

需要一个虚拟头结点，这样可以删除任意的节点，否则如果只有一个节点并删除自己，则需要单独处理

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int length = GetLength(head);
        ListNode* cur = new ListNode(0, head);
        ListNode* dummy = cur;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode* ans = dummy->next;
        return ans;
    }

    int GetLength(ListNode* head)
    {
        int length = 0;
        while (head)
        {
            head = head->next;
            ++length;
        } 
        return length;
    }
};

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = GetLength(head);
        ListNode cur = new ListNode(0, head);
        ListNode dummy = cur;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

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

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        def GetLength(head : Optional[ListNode]) -> Optional[int]:
            length = 0
            while (head != None):
                head = head.next
                length += 1
            return length
        length = GetLength(head)
        cur = ListNode(0, head)
        dummy = cur
        for i in range(1, length + 1 -n):
            cur = cur.next
        cur.next = cur.next.next
        ans = dummy.next
        return ans

2. 栈

用一个栈去存储节点，之后弹出的第n个节点就是需要删除的地方

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* cur = new ListNode(0, head);
        ListNode* dummy = cur;
        stack<ListNode*> stk;
        while (cur != nullptr) 
        {
            stk.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; ++i) stk.pop();
        head = stk.top();
        head->next = head->next->next;
        return dummy->next;
    }
};

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cur = new ListNode(0, head);
        ListNode dummy = cur;
        Deque<ListNode> stk = new LinkedList<>();
        while (cur != null) 
        {
            stk.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) stk.pop();
        head = stk.peek();
        head.next = head.next.next;
        return dummy.next;
    }
}

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        cur = ListNode(0, head)
        dummy = cur
        stk = list()
        while (cur != None): 
            stk.append(cur)
            cur = cur.next
        for i in range(n): stk.pop()
        head = stk[-1]
        head.next = head.next.next
        return dummy.next

3. 双指针

使用两个指针，快指针比慢指针多n个节点，快指针到达末尾则慢指针位置就是需要处理的地方

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* pre = new ListNode(0, head);
        ListNode* slow = pre;           // 不从head开始的原因在于，可以刚好到达倒数第n节点的前继结点
        ListNode* fast = head;
        for (int i = 0; i < n; ++i) fast = fast->next;
        while (fast != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return pre->next;
    }
};

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

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        pre = ListNode(0, head)
        slow = pre         
        fast = head
        for i in range(n): fast = fast.next
        while (fast != None):
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return pre.next

四：两两交换链表中的节点

1. 递归

终止条件为末尾只有单个节点或没有节点，一个递归需要处理两个节点

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* n1 = head->next;
        head->next = swapPairs(n1->next);
        n1->next = head;
        return n1;
    }
};

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode n1 = head.next;
        head.next = swapPairs(n1.next);
        n1.next = head;
        return n1;
    }
}

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if (head == None or head.next == None): return head
        n1 = head.next
        head.next = self.swapPairs(n1.next)
        n1.next = head
        return n1

2. 迭代

我们定义一个前继结点，依次交换后面的两个节点，然后前继结点向前移动两个位置

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* pre = new ListNode(0, head);
        ListNode* cur = pre;
        while (cur->next != nullptr && cur->next->next != nullptr)
        {
            ListNode* n1 = cur->next;
            ListNode* n2 = cur->next->next;
            cur->next = n2;
            n1->next = n2->next;
            n2->next = n1;
            cur = n1;
        }
        return pre->next;
    }
};

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0, head);
        ListNode cur = pre;
        while (cur.next != null && cur.next.next != null)
        {
            ListNode n1 = cur.next;
            ListNode n2 = cur.next.next;
            cur.next = n2;
            n1.next = n2.next;
            n2.next = n1;
            cur = n1;
        }
        return pre.next;
    }
}

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = ListNode(0, head)
        cur = pre
        while (cur.next != None and cur.next.next != None):
            n1 = cur.next
            n2 = cur.next.next
            cur.next = n2
            n1.next = n2.next
            n2.next = n1
            cur = n1
        return pre.next

五：随机链表的复制

1. 回溯+哈希表

该题的难度在于随机指针的处理，因为拷贝节点时，随机指针指向的节点可能还未创建，一种方法是先不拷贝随机指针，在第二次循环中再拷贝，或者利用递归的思想反向处理

class Solution {
public:
    unordered_map<Node*, Node*> hashMap;
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return head;
        if (!hashMap.count(head))
        {
            Node* newNode = new Node(head->val);
            hashMap[head] = newNode;
            newNode->next = copyRandomList(head->next);     // 到这里完成了除随机指针的拷贝
            newNode->random = copyRandomList(head->random);		// 等效于第二次遍历，此时节点已完成创建
        }
        return hashMap[head];
    }
};

class Solution {
    public Map<Node, Node> hashMap = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head == null) return head;
        if (hashMap.containsKey(head) == false)
        {
            Node newNode = new Node(head.val);
            hashMap.put(head, newNode);
            newNode.next = copyRandomList(head.next);     
            newNode.random = copyRandomList(head.random);     
        }
        return hashMap.get(head);
    }
}

class Solution:
    def __init__(self):
        self.hashMap = {}		# 这里初始化
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if (head == None): return head
        if (head not in self.hashMap):
            newNode= Node(head.val)
            self.hashMap[head] = newNode
            newNode.next = self.copyRandomList(head.next)     
            newNode.random = self.copyRandomList(head.random)     
        return self.hashMap[head]

2. 迭代+拆分

将每一个拷贝后的节点作为原节点的后继结点，随机指针则为原指针的随机指针节点的后继位置，空除外

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        Node* newHead = nullptr;
        for (Node* start = head; start != nullptr; start = start->next->next)		// 建立复制链表
        {
            Node* newNode = new Node(start->val);
            newNode->next = start->next;
            start->next = newNode;
        }
        for (Node* start = head; start != nullptr; start = start->next->next)		// 对随机指针赋值
        {
            if (start->random != nullptr) start->next->random = start->random->next;
            else start->next->random =nullptr;
        }
        newHead = head->next;
        for (Node* start = head; start != nullptr; start = start->next)			// 恢复原链表，连接新链表
        {
            Node* newNode = start->next;
            start->next = start->next->next;
            newNode->next = (newNode->next != nullptr) ? newNode->next->next : nullptr;
        }
        return newHead;
    }
};

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node newHead = null;
        for (Node start = head; start != null; start = start.next.next)		
        {
            Node newNode = new Node(start.val);
            newNode.next = start.next;
            start.next = newNode;
        }
        for (Node start = head; start != null; start = start.next.next)		
        {
            if (start.random != null) start.next.random = start.random.next;
            else start.next.random =null;
        }
        newHead = head.next;
        for (Node start = head; start != null; start = start.next)			
        {
            Node newNode = start.next;
            start.next = start.next.next;
            newNode.next = (newNode.next != null) ? newNode.next.next : null;
        }
        return newHead;
    }
}

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if (head == None): return None
        start = head
        while start:	
            newNode = Node(start.val)
            newNode.next = start.next
            start.next = newNode
            start = newNode.next
        start = head
        while start:	
            if (start.random != None): start.next.random = start.random.next
            else: start.next.random = None
            start = start.next.next
        newHead = head.next
        start = head
        while start:		
            newNode = start.next
            start.next = start.next.next
            if newNode.next:
                newNode.next = newNode.next.next
            start = start.next
        return newHead