[剑指Offer] Day 11: Linked List

Authored by Tony Feng

Created on April 22nd, 2022

Last Modified on April 22nd, 2022

Task 1 - Q18. 删除链表的节点

Question

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if not head: return head
        
        node = ListNode(0) # dummy node
        node.next = head
        pre = node
        while head:
            if head.val != val:
                pre = pre.next
                head = head.next
            else:
                pre.next = head.next
                return node.next
        return node.next

Explanation

Time Complexity: O(N)
Space Complexity: O(1)

Task 2 - Q22. 链表中倒数第k个节点

Question

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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

class Solution: # Fast & Slow Pointers
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        fast, slow = head, head

        # Let the Fast go through k nodes 
        while fast and k > 0: 
            fast = fast.next
            k = k - 1
            
        while fast:
            fast = fast.next
            slow = slow.next
        
        return slow

Explanation

Time Complexity: O(N)
Space Complexity: O(1)