[编程练习] 链表

1. 反转链表：Leetcode 206

Approach 1: 使用2个指针

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution:
 8     def reverseList(self, head: ListNode) -> ListNode:
 9         if not head or not head.next: return head
10         p1 = head
11         p2 = p1.next
12         p1.next = None
13         while p2.next is not None:
14             p3 = p2.next
15             p2.next = p1
16             p1 = p2
17             p2 = p3
18         p2.next = p1
19         return p2

Beats: 89.94%

Approach 2: 递归

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution:
 8     def reverseList(self, head):
 9         """
10         :type head: ListNode
11         :rtype: ListNode
12         """
13         if head is None or head.next is None: return head
14         p = self.reverseList(head.next)
15         head.next.next = head
16         head.next = None
17         return p

Beats: 66.67%

2. 回文链表： Leetcode 234

Given a singly linked list, determine if it is a palindrome.

Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?

Approach 1. 反转前半部分链表

用快慢指针记录链表中间节点

在前向遍历时，利用rev反转左半部分链表

最后，将左右部分链表遍历比较

Time complexity: O(n)

Space complexity: O(1)

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

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        rev = None
        slow = fast = head
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
        if fast is not None:
            slow = slow.next
        while rev is not None and rev.val == slow.val:
            slow = slow.next
            rev = rev.next
        return not rev

该代码复制了Leetcode中提交用时最少的代码。

Approach 2. 部分压栈

用快慢指针记录链表中间节点；

前向遍历时，用数组逆序保存节点值(通过insert(0, node.val))直到中间节点为止；

最终依次比较数组的值(即左半部分链表逆序), 与右半部分链表的值。

Time complexity: O(n)

Space complexity: O(n / 2)

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution:
 8     def isPalindrome(self, head: ListNode) -> bool:
 9         if not head or not head.next: return True
10         new_list = []
11         
12         slow = fast = head
13         while fast and fast.next:
14             new_list.insert(0, slow.val)
15             slow = slow.next
16             fast = fast.next.next
17             
18         if fast: # odd
19             slow = slow.next
20         
21         for val in new_list:
22             if val != slow.val:
23                 return False
24             slow = slow.next
25         return True