Linked List 链表。

面试时要是有链表相关题目,需要问清楚是单链表还是双链表、有没有可能有环。

# 亿点点练习题

# 206. Reverse Linked List

最基础的反转链表。

lc206-1.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur, suc = None, head, head.next if head else None 
        while cur: 
            cur.next = pre 
            pre, cur, suc = cur, suc, suc.next if suc else None 
        return pre
lc206-2.cpp
/**
 * 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* reverseList(ListNode* head) {
        if (!head) return head; 
        ListNode* pre = nullptr; 
        while (head) tie(head->next, pre, head) = tuple(pre, head, head->next); 
        return pre; 
    }
};

# 92. Reverse Linked List II

反转对应区间的链表。用常规做法很容易出错,可以设想每一步的操作都是把当前节点放到已反转的链表的最前面。

lc92-1.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(-1, head) 
        pre, cur = dummy, head
        for _ in range(left - 1): 
            pre, cur = pre.next, cur.next 
        for _ in range(right - left): 
            tmp = cur.next 
            cur.next = tmp.next 
            tmp.next = pre.next 
            pre.next = tmp 
        return dummy.next

# 25. Reverse Nodes in k-Group

按照 k 个一组反转链表。一直不觉得这道题有 hard 的程度。

lc25-1.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        hair = ListNode(-1, head) 
        cnt = 0 
        pre, cur = hair, head 
        while True: 
            if cnt > 0 and cnt % k == 0: 
                while cur.next != head: 
                    tmp = cur.next 
                    cur.next = tmp.next 
                    tmp.next = pre.next 
                    pre.next = tmp 
                pre = cur 
                cur = cur.next 
            if not head: break 
            head = head.next 
            cnt += 1 
        return hair.next
lc25-2.cpp
/**
 * 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* reverseKGroup(ListNode* head, int k) {
        ListNode *hair = new ListNode(0, head); 
        int cnt = 0; 
        ListNode *pre = hair, *cur = head; 
        while (1) {
            
            if (cnt > 0 && cnt % k == 0) {
                while (cur->next != head) {
                    ListNode *tmp = cur->next; 
                    cur->next = tmp->next; 
                    tmp->next = pre->next;
                    pre->next = tmp; 
                }
                pre = cur; 
                cur = cur->next; 
            }
            if (!head) break; 
            head = head->next; 
            cnt++; 
        }
        return hair->next; 
    }
};
  • 要注意 if 判断时有一个 cnt > 0 ,要不然一开始 cnt == 0 时就会进入。
  • 相比写成 while head ,外层循环写成 while True 有一个好处,当最后 head == None and cnt > 0 and cnt % k == 0 时仍然要进行一次反转, while True 仍然会进行处理,处理完在用 if not head: break 跳出。否则还要再外循环外面加上一个判断处理这个情况。

发现类似的思路很清晰,在做链表反转的时候想成这个过程:不断把下一个结点提到最前面。

reverse_linked_list.py
def reverseList(head, foot): 
    hair = ListNode(-1, head) 
    pre, cur = hair, head 
    while cur.next != foot: 
        tmp = cur.next 
        cur.next = tmp.next 
        tmp.next = pre.next 
        pre.next = tmp 
    # 这里 pre == hair, cur.next == foot 
    return hair.next

循环中的这四个表达式非常好记。

# 2074. Reverse Nodes in Even Length Groups

之前的周赛题,将链表结点分组,每组结点个数从 1 开始递增,要是有偶数个结点的话就将这组结点反转。

先贴一个之前写的代码:

lc2074-1.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseLength(self, head, length): 
        if not head: return None 
        prev, curr, succ = head, head, head.next 
        for i in range(1, length): 
            if not succ: break 
            curr = succ 
            succ = succ.next 
            curr.next = prev 
            prev = curr 
        head.next = succ 
        return curr 
    
    def countGroup(self, head, group): 
        cnt = 0 
        while head and cnt < group: 
            cnt += 1 
            head = head.next 
        return cnt 
    
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        group = 1 
        groupCnt = 0 
        curr = head 
        while curr:  
            groupCnt += 1 
            if group == groupCnt: 
                if self.countGroup(curr.next, group + 1) % 2 == 0: 
                    curr.next = self.reverseLength(curr.next, group + 1) 
                group += 1 
                groupCnt = 0 
            curr = curr.next
        # if lastGroupEnd and groupCnt % 2 == 1 and group % 2 == 1: 
        #     lastGroupEnd.next = self.reverseLength(lastGroupEnd.next, groupCnt + 1) 
        return head

现在看来不用这么麻烦。用类似于上面一题的方法可以写得很短。

lc2074-2.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        hair = ListNode(0, head) 
        pre, cur = hair, head 
        cnt, group = 0, 1  
        while True: 
            
            if cnt > 0 and cnt % group == 0 or (not head and cnt % 2 == 0): 
                if group % 2 == 0 or (not head and cnt % 2 == 0): 
                    while cur.next != head: 
                        tmp = cur.next 
                        cur.next = tmp.next 
                        tmp.next = pre.next 
                        pre.next = tmp 
                while cur != head: 
                    pre = cur 
                    cur = cur.next 
                # pre, cur = last_head, head
                # this is wrong because the previous node of head has changed when we do the reverse 
                cnt = 0 
                group += 1 
            
            if not head: break 
            head = head.next 
            cnt += 1 
        return hair.next

这种写法要注意:

  • pre 和 cur 的更新,这道题里要不要反转和 pre、cur 的更新是分开的,要注意他们的更新方式。
  • 最后一组如果是偶数个也要反转,所以要在 if 中加个特殊判断。

# 143. Reorder List

用数组存起来先……

lc143-1.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        nodes = [] 
        while head: 
            nodes.append(head) 
            head = head.next 
        first, last = 0, len(nodes) - 1 
        while first < last: 
            nodes[first].next = nodes[last] 
            nodes[last].next = nodes[first + 1] 
            first += 1 
            last -= 1 
        nodes[first].next = None
        return head

如果要用常量空间可以先找到中点,把后半段反转,然后再把这两段每隔一个合并。

lc143-2.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head: 
            return head 
        fast, slow = head, head 
        while fast and fast.next and fast.next.next: 
            fast, slow = fast.next.next, slow.next 
        cur, pre, slow.next = slow.next, None, None 
        while cur: 
            cur.next, pre, cur = pre, cur, cur.next 
        while head and pre: 
            head.next, pre.next, head, pre = pre, head.next, head.next, pre.next