Linked List

（单）链表是由节点和指针构成的数据结构，每个节点存有一个值，和一个指向下一个节点的指针，因此很多链表问题可以用递归来处理。不同于数组，链表并不能直接获取任意节点的值，必须要通过指针找到该节点后才能获取其值。同理，在未遍历到链表结尾时，我们也无法知道链表的长度，除非依赖其他数据结构储存长度。LeetCode 默认的链表表示方法如下。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

翻转链表

描述

翻转一个链表。

示例

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

解法

迭代法：我们可以使用三个指针，分别指向当前节点，前一个节点和后一个节点，然后不断地将当前节点的指针指向前一个节点，直到当前节点为空。

def reverseList(head):
    prev = None
    while head:
        temp = head.next  
        head.next = prev
        # 更新prev和head
        prev = head
        head = temp
    return prev

递归法：我们可以使用递归来翻转链表，递归的终止条件是当前节点为空或者下一个节点为空，然后不断地将当前节点的指针指向前一个节点。

def reverseList(head):
    if not head or not head.next:
        return head
    p = reverseList(head.next) # p 永远是最后一个节点
    # 下面两行，让下一节点指向当前节点，当前节点指向None
    head.next.next = head
    head.next = None
    return p

Merge Two Sorted Lists

Description

Merge two sorted linked lists and return them as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Solution1: Recursion

def mergeTwoLists(l1, l2):
    if not l1 or not l2:　# 如果有一个链表为空，直接返回另一个链表
        return l1 or l2　# 如果l1为空，返回l2，否则返回l1
    if l1.val < l2.val: # 如果l1的值小于l2的值，l1的下一个节点指向mergeTwoLists(l1.next, l2)
        l1.next = mergeTwoLists(l1.next, l2)
        return l1 
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

假设我们有两个已排序的链表 l1 和 l2，分别如下所示：

l1: 1 -> 3 -> 5 -> None
l2: 2 -> 4 -> 6 -> None

我们要将这两个链表合并成一个新的有序链表。下面是递归合并的过程：

递归层级	l1	l2	操作	返回结果
初始	1 -> 3 -> 5 -> None	2 -> 4 -> 6 -> None	比较 1 和 2，选择 1，然后递归合并 l1.next 和 l2	1 -> mergeTwoLists(3 -> 5 -> None, 2 -> 4 -> 6 -> None)
第一层	3 -> 5 -> None	2 -> 4 -> 6 -> None	比较 3 和 2，选择 2，然后递归合并 l1 和 l2.next	1 -> 2 -> mergeTwoLists(3 -> 5 -> None, 4 -> 6 -> None)
第二层	3 -> 5 -> None	4 -> 6 -> None	比较 3 和 4，选择 3，然后递归合并 l1.next 和 l2	1 -> 2 -> 3 -> mergeTwoLists(5 -> None, 4 -> 6 -> None)
第三层	5 -> None	4 -> 6 -> None	比较 5 和 4，选择 4，然后递归合并 l1 和 l2.next	1 -> 2 -> 3 -> 4 -> mergeTwoLists(5 -> None, 6 -> None)
第四层	5 -> None	6 -> None	5 比 6 小，然后递归合并 l1.next 和 l2	1 -> 2 -> 3 -> 4 -> 5 -> mergeTwoLists(None, 6 -> None)
第五层	None	6 -> None	l1 为空，返回 l2	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None

最后得到的合并后的链表为：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None。

Solution2: Iteration

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    cur = dummy
    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 dummy.next

Linked List

# 翻转链表

# 描述

# 示例

# 解法

# Merge Two Sorted Lists

# Description

# Example

# Solution1: Recursion

# Solution2: Iteration