21. Merge Two Sorted Lists

思路：遍历两个链表，将链表中较小的值存到新的链表中

# @lc app=leetcode id=21 lang=python3
#
# [21] Merge Two Sorted Lists
#

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

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        if not l1 or not l2:
            return l1 or l2
        head = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        # 这种写法很简练
        cur.next = l1 or l2
        return head.next

22. Generate Parentheses

思路：经典的回溯问题，递归终止条件就是字符串的长度是,其余的限制条件是剩余左括号的数量一定要小于右括号的数量

#
# @lc app=leetcode id=22 lang=python3
#
# [22] Generate Parentheses
#

# @lc code=start


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        self.dfs(n, n, n, "", res)
        return res 
    def dfs(self, n, left, right, path, res):
        if len(path) == 2 * n:
            res.append(path[:])
            return 
        if left > 0:
            self.dfs(n, left-1, right, path+"(", res)
        # 这里右括号一定是要大于 左括号，不能有等号
        if right > left:
            self.dfs(n, left, right-1, path+")", res)

23. Merge k Sorted Lists

思路：分治的思想，将list中的链表分为两组，分别采用21题的思路，完成合并。

#
# @lc app=leetcode id=23 lang=python3
#
# [23] Merge k Sorted Lists
#

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

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return
        if len(lists) == 1:
            return lists[0]
        mid = len(lists)//2
        l = self.mergeKLists(lists[:mid])
        r = self.mergeKLists(lists[mid:])
        return self.merge(l, r)


    def merge(self, l, r):
        dummy = cur = ListNode(0)
        while l and r:
            if l.val < r.val:
                cur.next = l
                l = l.next
            else:
                cur.next = r
                r = r.next
            cur = cur.next
        cur.next = l or r
        return dummy.next

24. Swap Nodes in Pairs

image.png

# @lc app=leetcode id=24 lang=python3
#
# [24] Swap Nodes in Pairs
#
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummyHead = ListNode(0)
        dummyHead.next = head 
        p = dummyHead
        while p.next and p.next.next:
            node1 = p.next 
            node2 = p.next.next 
            next = node2.next 
           # p node2 node1 next
            node2.next = node1 
            node1.next = next 
            p.next = node2
            p = node1 
        return dummyHead.next 

25. Reverse Nodes in k-Group

思路:首先对链表中的元素进行计数，计满k个之后，就开始对这k个数进行翻转操作，要注意最后一个节点的处理。

# @lc app=leetcode id=25 lang=python3
#
# [25] Reverse Nodes in k-Group
#
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if not head or k ==1:
            return head 
        dummy = ListNode(0)
        dummy.next = head 
        count = 0 
        p1 = dummy 
        p2 = head 
        while p2:
            count +=1 
            if count <k:
                p2 = p2.next 
            else:
                next_ = p2.next 
                p1 = self.reverse(p1, next_)
                count=0
                p2 = next_
        return dummy.next 
            
    def reverse(self, head, tail):
        last = head.next 
        cur = head.next 
        while cur and cur != tail:
            next_ = cur.next 
            tmp = head.next 
            head.next = cur 
            cur.next = tmp 
            cur = next_
        last.next = tail 
        return last