光

Life sucks, but you're gonna love it.

0%

Algorithm | LinkedList

Posted on In

啊，好像不怎么碰到Linked List使用的情况啊。之前上一个文章里总结的都是 Array的问题，其实在python里也叫list，所以就比较容易混淆。array list 和linked list的区别就在于，array list有直接的index 可以在 O(1) 的时间复杂度下找到想要找的数值。但是linked list就需要从头开始找。但是linked list比较方便于插入和删除，只需要找到对应的点改变前后两个node的.next属性就可以了，但是array list就很麻烦，需要对每一个list中的值进行移动。

NO.2 Add Two Numbers

题目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解题思路

这道题其实就是简单的运用linked list的方面，对于我自己，需要注意的点是：

  • 当两个数相加的和大于10 的时候需要进位，熟练运用 % 和 / 运算，
  • 需要加dummyhead

第一点是我可以想到的，第二点我查了一些帖子，都是在说为什么需要dummy head。是因为如果是doubly linked list时，有了dummyhead就不需要多去判定原来的head node是不是为空。【这类问题还没遇到】另一个原因就是，list整体需要变动，就是我们这道题，定义的两位之和需要不断向后移动来更新.next的内容

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        addto = 0
        l = ListNode(0)
        dummyhead = l
        
        while l1 and l2:
            l.next = ListNode((addto + l1.val + l2.val) % 10)
            addto = (addto + l1.val + l2.val) / 10
            l = l.next
            l1 = l1.next
            l2 = l2.next
            
        while l1:
            l.next = ListNode((addto + l1.val) % 10)
            addto = (addto + l1.val) / 10
            l = l.next
            l1 = l1.next
            
        while l2:
            l.next = ListNode((addto + l2.val) % 10)
            addto = (addto + l2.val) / 10
            l = l.next
            l2 = l2.next
        print(addto)   
        if addto:
            l.next = ListNode(addto)
            
        return dummyhead.next

应该可以再合并一些情况，但是思路就是这样。

NO.19 Remove Nth Node from the end of the list.

>

解题思路

简单的来说可以先把head中的所有node遍历一遍存在一个list中，然后再遍历一遍根据for循环来找到倒数第n个值，也就是要判定 i == len(vals) - n，把其他的值都存在新的listnode中。但是这部分要遍历两遍。

可以一遍吗？

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 遍历两遍
def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        vals = []
        while head:
            vals.append(head.val)
            head = head.next
        
        newhead = ListNode(0)
        dummy = newhead
        for i in range(len(vals)):
            if i == len(vals) - n:
                continue
            newhead.next = ListNode(vals[i])
            newhead = newhead.next
            
        return dummy.next
# 遍历一遍
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        
        new1 = dummy
        new2 = dummy
        
        while n>0:
            new1 = new1.next
            n = n - 1
            
        while new1.next:
            new1 = new1.next
            new2 = new2.next
        new2.next = new2.next.next
        
        return dummy.next

NO.24

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# Change numbers
def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next: return head
        
        dummy = ListNode(0)
        new = dummy        
        while head and head.next:
            val1 = head.val
            head = head.next
            val2 = head.val
            head = head.next
            
            new.next = ListNode(val2)
            new = new.next
            new.next = ListNode(val1)
            new = new.next
        
        new.next = head
        return dummy.next
# Change nodes.
def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next: return head
        
        dummy = ListNode(0)
        dummy.next = head
        
        new = dummy
        
        while new.next and new.next.next:
            first = new.next
            second = new.next.next
            new.next = second
            first.next = second.next
            second.next = first
            
            new = new.next.next
 
        return dummy.next

NO.