Array & Linked List [TOC]

知识点

  1. Array Access: O(1) Insert: 平均 O(n) Delete: 平均 O(n)

  2. Linked List Access: O(n) Insert: O(1) Delete: O(1)

  3. Doubly Linked List space O(n) prepend O(1) append O(1) lookup O(n) insert O(1) delete O(1)

例题

206. Reverse Linked List

Reverse a singly linked list. Example:

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

Follow up:A linked list can be reversed either iteratively or recursively. Could you implement both?

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            cur.next, pre, cur = pre, cur, cur.next
        return pre
24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.You may not modify the values in the list’s nodes, only nodes itself may be changed.  Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

# 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:
        pre, pre.next = self, head
        while pre.next and pre.next.next:
            a = pre.next
            b = a.next
            pre.next, b.next, a.next, pre = b, a, b.next, a
        return self.next
141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.  Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node.

0ac1c374da73504066d5990dc7ea7cbb.png Example 2:

Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.

80070274b753fb6017362bc5b5bb1195.png Example 3:

Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.

faeeb9031a07904b5fb959efd28ee031.png Follow up:Can you solve it using O(1) (i.e. constant) memory?

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

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = slow = head
        while fast and slow and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False
142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.Note: Do not modify the linked list.  Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.

0ac1c374da73504066d5990dc7ea7cbb.png Example 2:

Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.

80070274b753fb6017362bc5b5bb1195.png Example 3:

Input: head = [1], pos = -1 Output: no cycle Explanation: There is no cycle in the linked list.

faeeb9031a07904b5fb959efd28ee031.png  Follow up: Can you solve it without using extra space?

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur = head
        nodes = set()
        while cur:
            if cur in nodes:
                return cur
            nodes.add(cur)
            cur = cur.next
        return None
25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. Example:

Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5 For k = 3, you should return: 3->2->1->4->5

Note: Only constant extra memory is allowed. You may not alter the values in the list’s nodes, only nodes itself may be changed.

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

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        pre, pre.next = self, head
        while True:
            node = pre
            tmps = dict()
            for i in range(k):
                if node.next is None:
                    break
                node = node.next
                tmps[i] = node
            else:          
                pre.next = tmps[k-1]
                tmps[0].next = tmps[k-1].next
                pre = tmps[0]
                for i in range(k-1, 0, -1):
                    tmps[i].next = tmps[i-1]
                continue
            break
        return self.next