LeetCodeCampsDay3链表part01

主要与链表相关
记住：一般涉及到增删改操作，用虚拟头结点dummy_head都会方便很多，如果只能查的话，用不用虚拟头结点都差不多。

链表理论基础

建议：了解一下链表基础，以及链表和数组的区别

文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

203. 移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/

一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

思路

head是输入链表，是不动的；需要一个遍历的指针，可以使用index = head创建；
不断判断index.next的值是否等于val（因为，如果index.next.val等于val，可以通过操作，让index.next被删除）
最后判断下，如果head.val等于val，需要将head=head.next ；以免出现val=1, 但head返回是[1，2]的情况

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if head is None:
            return head
        
        index = head
        while index.next is not None:
            if val == index.next.val:
                index.next = index.next.next
            else:
                index = index.next
        if head.val == val:
            head = head.next
        return head

思路二

思路一有个缺点，需要单独写一段逻辑处理头结点的情况，可以设置一个虚拟头部dummy_head，其中dummy_head.next=head；从而原链表的所有节点都可以统一处理

代码二

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummpy_head = ListNode(next = head)
				# 同样需要index作为当前指针
        index = dummpy_head
        while index.next is not None:
            if val == index.next.val:
                index.next = index.next.next
            else:
                index = index.next
        return dummpy_head.next

206. 反转链表

https://leetcode.cn/problems/reverse-linked-list/

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

思路一

至少需要三个辅助节点，pre, current, current_next(temp)

先记录current.next到temp
不断将current.next设置为pre
pre转成current；current转成temp

代码一

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:        
        current = head
        pre = None
        
        while current is not None:
            temp = current.next
            current.next = pre
            pre = current
            current = temp
            
        return pre

思路二（递归）

退出条件：如果head为空/head.next为空，则直接返回haed，因为它已经反转了

让递归函数输入head.next(即剩下链表)，返回结果为new_head；new_head会先变成原head链表最后一个元素，如[1,2,3,4,5]则new_head为5，且整个递归过程new_head一直为5

foo([1,2,3,4,5])

foo([1,foo([2,3,4,5])])

foo([1,foo([2,foo([3,4,5])])])

foo([1,foo([2,foo([3,foo([4,5])])])])

foo([1,foo([2,foo([3,foo([4,foo([5])])])])])

逐个分析下

foo([5])返回head，并且成为new_head
对于foo([4,foo([5])])，new_head = 5；head.next.next = head 意为将4.next.next（原来为5）设置为4，即5.next = 4；且head.next = None，即4.next = None；这里把4当成反转后的最后一个节点
对于foo([3,foo([4,foo([5])])])，new_head = 5; head.next.next = head意为将3.next.next(原为4)设置为3，即4.next = 3且head.next = None，即3.next = None；这里把3当成反转后的最后一个节点
对于foo([2,foo([3,foo([4,foo([5])])])])，new_head = 5; head.ext.next = head意为将2.next.next(原为3)设置为2，即3.next = 2且head.next = None，即2.next = None；这里把2当成反转后的最后一个节点
对于foo([1,foo([2,foo([3,foo([4,foo([5])])])])])，new_head = 5; head.ext.next = head意为将1.next.next(原为2)设置为1，即2.next = 1且head.next = None，即1.next = None；这里把1当成反转后的最后一个节点

从而完成递归的反转链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:        
        def foo(head: Optional[ListNode]):
            if head is None or head.next is None:
                return head
            # new_head会先变成原head链表最后一个元素
            # [1,2,3,4,5]则new_head为5，且一直为5
            new_head = foo(head.next)
            # 反转两个节点
            head.next.next = head
            # 反转后的最后一个节点的next设置为None
            head.next = None

            return new_head

        return foo(head)

时间复杂度O(n)，其中n是链表节点数，每个节点被访问一次

空间复杂度O(N)，递归调用栈的空间，最坏的情况下，stack深度为n

707. 设计链表

https://leetcode.cn/problems/design-linked-list/

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

思路

先确定使用单链表，包含head和L(表示节点个数)
addAtHead设置借用203.移除链表元素里dummy_head思想即可
addAtIndex才是核心需要设置的东西
1. 如果index为0，addAtIndex直接调用addAtHead；
2. 如果index > self.L or index < 0 直接返回
3. 如果index有效，寻找index前一节点current，令current.next = newNode
addAtTail直接调用addAtIndex就行，传入self.L,val
deleteAtIndex难度不大
1. Index == 0，直接跳过head即可
2. Index >= self.L 直接返回
3. Index有效时，找到index前一节点current，令current.next = current.next.next

另外，定义个函数__getIndexPreNode，用来找到index的前一个节点；因为有至少三个函数需要调用到它

def __getIndexPreNode(self, node, index):
        current = node
        for _ in range(index - 1):
            current = current.next
        return current

__printList用来打印当前链表

def __printList(self, node):
        caller_name = inspect.stack()[1].function
        current = self.head
        print(f"caller_name: {caller_name}")
        while current.next:
            print(current.val, end = ' ')
            current = current.next
        print(f", self.L {self.L}")
        print(" ")

代码

class ListNode:
    def __init__(self,val = 0, next = None):
        self.val = val
        self.next = next
import inspect
class MyLinkedList:
    def __init__(self):
        self.head = ListNode()
        self.L = 0

    def __getIndexPreNode(self, node, index):
        current = node
        for _ in range(index - 1):
            current = current.next
        return current

    def __printList(self, node):
        caller_name = inspect.stack()[1].function
        current = self.head
        print(f"caller_name: {caller_name}")
        while current.next:
            print(current.val, end = ' ')
            current = current.next
        print(f", self.L {self.L}")
        print(" ")

    def get(self, index: int) -> int:
        if index >= self.L or index < 0:
            return -1
        if index == 0:
            return self.head.val

        current = self.__getIndexPreNode(self.head, index)
        # self.__printList(self.head)
        return current.next.val

    def addAtHead(self, val: int) -> None:
        dummy_head = ListNode(val = val, next = self.head)
        self.head = dummy_head
        self.L += 1
        # self.__printList(self.head)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.L, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.L or index < 0:
            return -1
        
        if index ==0 :
            return self.addAtHead(val)
        
        current = self.__getIndexPreNode(self.head, index)
        newNode = ListNode(val, current.next)
        current.next = newNode
        self.L += 1
        # self.__printList(self.head)

    def deleteAtIndex(self, index: int) -> None:
        if index >= self.L or index < 0:
            return 
        if index == 0:
            self.head = self.head.next
            self.L -= 1
            return
        current = self.__getIndexPreNode(self.head, index)
        current.next = current.next.next
        self.L -= 1
        # self.__printList(self.head)


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

改进版

其它思路不变，规定将head作为“dummy_head”
新增__getIndexNode函数，指获得Index对应节点
优点：代码更统一了，减少了需要额外讨论index==0以及index==self.L的情况！！所以，有dummy_head非常方便
因为head是dummy_head，所以__getIndexNode(index)得到的就是index的pre节点，和原版作用是一样的
所以get函数中需要传入head.next而不是head

一般涉及到增删改操作，用虚拟头结点dummy_head都会方便很多，如果只能查的话，用不用虚拟头结点都差不多。

代码二

class ListNode:
    def __init__(self,val = 0, next = None):
        self.val = val
        self.next = next
import inspect
class MyLinkedList:
    def __init__(self):
        self.head = ListNode()
        self.L = 0

    def __getIndexNode(self, node, index):
        current = node
        for _ in range(index):
            current = current.next
        return current

    def get(self, index: int) -> int:
        if index >= self.L or index < 0:
            return -1
				# 注意，这里传入head.next而不是head
        current = self.__getIndexNode(self.head.next, index)
        return current.val

    def addAtHead(self, val: int) -> None:
        self.head.next = ListNode(val = val, next = self.head.next)
        self.L += 1

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.L, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.L or index < 0:
            return -1
        
        current = self.__getIndexNode(self.head, index)
        current.next =  ListNode(val, current.next)
        self.L += 1
        # self.__printList(self.head)

    def deleteAtIndex(self, index: int) -> None:
        if index >= self.L or index < 0:
            return 

        current = self.__getIndexNode(self.head, index)
        current.next = current.next.next
        self.L -= 1
        # self.__printList(self.head)


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

链表理论基础

203. 移除链表元素

思路

代码

思路二

代码二

206. 反转链表

思路一

代码一

思路二（递归）

707. 设计链表

思路

代码

改进版

代码二

相关推荐