LeetCode review 1 LinkedList

发表于 |

  1. lc2 两数相加
    给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
    如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
    您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
    temp_sum计算每一位，flag计算进位，注意进位的处理。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution:
        def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
            if not l1:
                return l2
            if not l2:
                return l1
            res = ListNode(0)
            temp = res
            flag = 0
            while l1 or l2:
                temp_sum = 0
                if l1:
                    temp_sum += l1.val
                    l1 = l1.next
                if l2:
                    temp_sum += l2.val
                    l2 = l2.next
                temp_res = (temp_sum+flag) % 10
                flag = (temp_sum+flag) // 10
                res.next = ListNode(temp_res)
                res = res.next
            if flag:
                res.next = ListNode(1)
            return temp.next

  2. lc19 删除链表的倒数第N个节点
    给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
    双指针的next指向head，第一个指针先向后移动n个位置，然后两个指针同时移动直到第一个指针移动到链表末端，此时第二个指针指向倒数第n+1个数，删除第二个指针的next节点即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution:
        def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
            res = ListNode(0)
            res.next = head
            p, q = res, res

            for _ in range(n):
                q = q.next
            
            while q.next:
                q = q.next
                p = p.next
            
            p.next = p.next.next
            return res.next