您现在的位置是：首页 >技术交流 >算法训练营第三天| 203.移除链表元素、707.设计链表、206.反转链表网站首页技术交流

算法训练营第三天| 203.移除链表元素、707.设计链表、206.反转链表

qq_41639001 2024-07-04 18:01:02
简介算法训练营第三天| 203.移除链表元素、707.设计链表、206.反转链表

目录

链表

  1. 链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

  2. 链表类型：单链表、双链表、循环链表

  3. 数组是在内存中是连续分布的，但是链表在内存中是散乱分布的。

  4. 链表的定义

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

  5. 数组与链表的性能分析


    数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

    链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

    以上关于链表内容摘自代码随想录

203.移除链表元素

  1. 解题思路

    定义一个虚拟头节点，作用是定位链表头节点，定义一个指针，从虚拟头节点位置开始遍历链表，当当前节点的下一个节点的 val == target 时，使当前节点的next指向下一个节点的next的next，直到遍历结束，返回虚拟头节点的next值

  2. 代码实现

    def removeElements(head, val):
	# 定义虚拟头节点
	dummy_head = ListNode(next=head)
	# 遍历节点
	current = dummy_head
	while current.next:
		if current.next.val == val:
			current.next = current.next.next
		else:
			current = current.next
	return dummy_head.next

  3. 难点

    定义虚拟头节点 dummy_head = ListNode(next=head)，其next指向head头节点，再 current = dummy_head，通过current.next循环条件，统一遍历链表

  4. 时间复杂度、空间复杂度分析

    时间复杂度O(n)、空间复杂度O(1)

707.设计链表

  1. 解题思路

    单链表定义虚拟头节点，双链表定义头节点和尾节点

  2. 代码实现

    单链表法：

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

class MyLinkedList:

    def __init__(self):
        self.dummy_head = ListNode()
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index > self.size - 1:
            return -1
        current = self.dummy_head
        for i in range(index):
            current = current.next
        return current.next.val

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

    def addAtTail(self, val: int) -> None:
        current = self.dummy_head
        while current.next:
            current = current.next
        current.next = ListNode(val)
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return
        current = self.dummy_head
        for i in range(index):
            current = current.next
        current.next = ListNode(val,current.next)
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index > self.size - 1:
            return 
        current = self.dummy_head
        for i in range(index):
            current = current.next
        current.next = current.next.next
        self.size -= 1
        
    def __str__(self):
        current = self.dummy_head
        li = []
        while current.next:
            li.append(str(current.next.val))
            current = current.next
        return ", ".join(li)
        

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

    双链表法（一）：

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


class MyLinkedList:

    def __init__(self):
        self.dummy_head = ListNode()
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index > self.size - 1:
            return -1
        current = self.dummy_head
        for i in range(index):
            current = current.next
        return current.next.val

    def addAtHead(self, val: int) -> None:
        newNode = ListNode(val,self.dummy_head,self.dummy_head.next)
        if self.dummy_head.next: self.dummy_head.next.pre = newNode
        self.dummy_head.next = newNode
        self.size += 1

    def addAtTail(self, val: int) -> None:
        current = self.dummy_head
        while current.next:
            current = current.next
        current.next = ListNode(val,current,current.next)
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return
        current = self.dummy_head
        for i in range(index):
            current = current.next
        newNode = ListNode(val,current,current.next)
        if current.next: current.next.pre = newNode
        current.next = newNode
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index > self.size - 1:
            return
        current = self.dummy_head
        for i in range(index):
            current = current.next
        # 先修改 pre 指针，再修改 next 指针
        if current.next.next: current.next.next.pre = current
        current.next = current.next.next
        self.size -= 1

    def __str__(self):
        current = self.dummy_head
        li = []
        while current.next:
            li.append(str(current.next.val))
            current = current.next
        return ", ".join(li)


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

    双链表法（二）：摘自代码随想录

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


class MyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

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

        if index < self.size // 2:
            current = self.head
            for i in range(index):
                current = current.next
        else:
            current = self.tail
            for i in range(self.size - index - 1):
                current = current.prev

        return current.val

    def addAtHead(self, val: int) -> None:
        new_node = ListNode(val, None, self.head)
        if self.head:
            self.head.prev = new_node
        else:
            self.tail = new_node
        self.head = new_node
        self.size += 1

    def addAtTail(self, val: int) -> None:
        new_node = ListNode(val, self.tail, None)
        if self.tail:
            self.tail.next = new_node
        else:
            self.head = new_node
        self.tail = new_node
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return

        if index == 0:
            self.addAtHead(val)
        elif index == self.size:
            self.addAtTail(val)
        else:
            if index < self.size // 2:
                current = self.head
                for i in range(index - 1):
                    current = current.next
            else:
                current = self.tail
                for i in range(self.size - index):
                    current = current.prev
            new_node = ListNode(val, current, current.next)
            current.next.prev = new_node
            current.next = new_node
            self.size += 1

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

        if index == 0:
            self.head = self.head.next
            if self.head:
                self.head.prev = None
            else:
                self.tail = None
        elif index == self.size - 1:
            self.tail = self.tail.prev
            if self.tail:
                self.tail.next = None
            else:
                self.head = None
        else:
            if index < self.size // 2:
                current = self.head
                for i in range(index):
                    current = current.next
            else:
                current = self.tail
                for i in range(self.size - index - 1):
                    current = current.prev
            current.prev.next = current.next
            current.next.prev = current.prev
        self.size -= 1

    def __str__(self):
        li = []
        current = self.head
        for i in range(self.size):
            li.append(str(current.val))
            current = current.next
        return ", ".join(li)

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

  3. 难点

    1. 单链表新增节点：A、B节点中新增C节点，首先定义C节点，其中 C.next = A.next，再设置A节点的next，即 A.next = C
    2. 单链表删除节点：A、C、B节点中删除C节点，设置 A.next = A.next.next
    3. 双链表新增节点：A、B节点中新增C节点，首先定义C节点，其中 C.pre = A, C.next = A.next，再设置B节点的pre，即 A.next.pre = C，最后设置A节点的next，即 A.next = C ，需注意：当新增C节点在头位置或是末尾位置时，其中pre或next值为None
    4. 双链表删除节点：A、C、B节点中删除C节点，先设置B节点的pre，即 B.pre = C.pre，再设置A节点的next，即 A.next = C.next，需注意：当删除C节点在头位置或是末尾位置时，其B.pre或A.next值为None

  4. 时间复杂度、空间复杂度分析

    时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)
    空间复杂度: O(n)

206.反转链表

  1. 解题思路

    1. 双指针法；
      前指针 pre = None，当前指针 cur = head
      遍历链表，首先记录 temp = cur.next，再反转当前指针，即 cur.next = pre
      而后 pre、cur 右移，即 pre = cur，cur = temp
      直到 cur = None 结束，返回 pre

  2. 代码实现

    双指针法：

    def reverseList(head):
    pre,cur = None,head
    while cur:
        temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    return pre

    递归方法：

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

  3. 难点

  4. 时间复杂度、空间复杂度分析

    时间复杂度O(n)、空间复杂度O(n)

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐