[数据结构与算法]链表做题总结（五）[148，206]

148. 排序链表

思路：递归实现链表归并排序，具体步骤见代码
注意：对于递归的理解还是不够透彻，可以将递归函数一直推算到极限，比如本题最终每个子链表分割到只有一个结点的时候，此时结合代码去思考。递归是一个套娃！递归到最小单位再思考怎么写代码，还要注意跳出递归的条件。
在合并队列的时候，要秉承由小到大的原则，所以每循环一次只加一个节点，另一个节点还要继续参与比较。
代码：

 # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 递归终止条件
        if not head or not head.next:
            return head

        fast=head.next
        slow=head
        # 偶数个节点时slow为左边
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next

        # 从中间切分开
        mid=slow.next
        slow.next=None

        # 递归分割，输入当前链表左端点 head 和中心节点 slow 的下一个节点
        left=self.sortList(head)
        right=self.sortList(mid)

        #合并
        h=res=ListNode(0)
        while left and right:
            if left.val < right.val:
                h.next=left
                left= left.next
            else:
                h.next=right
                right=right.next
            h=h.next
        h.next=left if left else right
        return res.next

206. 反转链表

思路：迭代方法已经没问题，重点理解递归
注意：在迭代中，第一个节点的next一定要为None(设pre=None即可)。在递归中，每迭代一次都要将 head.next=None。
代码：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 迭代
        pre=None
        cur=head
        while cur:
            next=cur.next
            cur.next=pre
            pre=cur
            cur=next
        return pre

        #递归

        # 递归出口
        if not head or not head.next:
            return head
        #假设后面的节点已经反转完成，则下一个要处理的节点是next
        newHead= reverseList(head.next)
        head.next.next=head
        # 要注意head的next指针要指向空，不然会有环
        head.next=None
        return newHead