LeetCode-算法-递归和回溯-第10天

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
具体题目链接

Python

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        newnode=ListNode()
        head=newnode
        while l1 and l2:
            if l1.val>l2.val:
                newnode.next=l2
                l2=l2.next
            else:
                newnode.next=l1
                l1=l1.next
            newnode=newnode.next
        newnode.next=l1 if l1 else l2
        return head.next

思路：通过新建一个newnode节点，进行逐步移动，head节点记录头部位置。通过循环判断来通过newnode来链接各个节点。最后若某个ListNode未到头，则通过newnode.next直接连接。

GO

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1==nil{
        return l2
    }
    if l2==nil{
        return l1
    }
    if l1.Val<l2.Val{
        l1.Next=mergeTwoLists(l1.Next, l2)
        return l1
    }else{
        l2.Next=mergeTwoLists(l1, l2.Next)
        return l2
    }
}

思路：通过递归方式实现。

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
具体题目链接

Python

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        head1=head
        front=None
        while head:
            next=head.next#记录下一个节点
            head.next=front#使当前节点指向前一个节点
            front=head#使前一个节点等于当前节点
            head=next#使当前节点挪动到下一个节点
        return front

思路：通过迭代实现，在遍历链表时，将当前节点的 \textit{next}next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

GO

func reverseList(head *ListNode) *ListNode {
    if head==nil || head.Next==nil{
        // head==nil判断是否为空节点， head.Next==nil如果只存在一个节点，则直接返回当前节点（0或1个节点数无需反转）
        return head
    }
    newhead:=reverseList(head.Next)//进行迭代
    head.Next.Next=head//每次只进行相邻的两个进行，是其完成head->node->head的闭环
    head.Next=nil//之后切断head->node，则只剩下node->head
    return newhead
}

思路：通过递归的方式实现。具体思路看注释。