数据结构与算法——链表
|
admin
|
2,928
|
0
|
未分类

1434 字
|
19 分钟
本文最后更新于 794 天前，其中的信息可能已经有所发展或是发生改变。

单链表

表域元素val保存着数据项，链接域next保存同一表里的下个节点的标识，P为表头变量/表头指针

单链表.png

插入新元素

  • 初始化新节点cur
  • 将cur的next字段链接到prev的下个节点
  • 将prev中的next字段链接到cur

单链表插新元素1.png

单链表插新元素2.png

在开头插入节点

  • 初始化一个新节点cur
  • 将新节点链接到原始头结点head
  • 将cur指定为head

单链表表头插入元素.png

删除操作

  • 找到cur的上一个结点prev及其下一个结点next

  • 链接prev到cur的下一个结点next

    单链表删除元素.png

在第一步中，要找到prev和next，需要从头结点开始遍历链表，才能找到prev，平均时间复杂度是$O(n)$

删除第一个节点

  • 给定原始链表和头结点head

  • 将头结点的下个节点指定为头结点head

    单链表删除头结点.png

单链表操作的复杂度

  • 创建链表：$O(1)$
  • 删除链表：在python里是$O(1)$
  • 判断表空：$O(1)$
  • 首端加入元素：$O(1)$
  • 尾端加入元素，要找到表的最后节点：$O(n)$
  • 定位插入元素：$O(n)$
  • 首端删除元素：$O(1)$
  • 尾端删除元素：$O(n)$
  • 定位删除元素：$O(n)$
  • 扫描、定位、遍历：$O(n)$

循环单链表

在链表对象里记录尾节点，这样可以同时支持$O(1)$的表头/表尾插入和$O(1)$的表头删除

循环单链表.png

双链表

双链表除了next字段，还有一个prev字段，指向当前节点的前一个节点

双链表.png

添加操作

  • 初始化一个新节点cur
  • 链接cur与prev的next，链接cur的prev与prev
  • 用cur重新链接prev和next

双链表的添加操作.png

删除操作

双链表删除操作.png

循环双链表

循环双链表.png

代码实现

单链表

单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。假设链表中的所有节点都是 0-index 的。在链表类中实现这些功能：

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
# 节点类，代表链表的每个节点
class Node(object):
    def __init__(self, x, next_=None):
        # 节点的值
        self.val = x
        # 节点的下个指向
        self.next = next_

# 链表类
class MyLinkedList(object):
    # 初始化
    def __init__(self):
        # 初始化头部节点
        self.head = None
        # 记录链表长度
        self.length = 0

    # 打印链表所有节点
    def print_all(self):
        p = self.head
        res = []
        res.append(p.val)
        while p.next:
            p = p.next
            res.append(p.val)
        print(res)

    # 根据索引index获得节点
    def get(self, index):
        '''
        获得第index个节点
        '''
        # 头部节点
        p = self.head
        # 若链表为空或index小于0，则返回-1
        if not p or index < 0:
            return -1
        # 遍历链表找到第index个节点
        while index >= 1:
            # 若index大于链表长度
            if p.next == None:
                return -1
            else:
                p = p.next
            index -= 1   
        return p.val

    def addAtHead(self, val):
        '''
        在头部添加节点
        '''
        # 新建值为val的节点，next指向head节点的next，然后将此节点指定为head节点
        self.head = Node(val, self.head)
        self.length += 1

    def addAtTail(self, val):
        '''
        在尾部添加节点
        '''
        # 如果链表为空，则在头部添加节点
        if self.head == None:
            self.head = Node(val)
            self.length += 1
            return
        # 链表不为空，先获得头部节点
        p = self.head
        # 遍历节点，找到最后一个节点
        while p.next is not None:
            p = p.next
        # 最后一个节点指向新建节点
        p.next = Node(val)
        self.length += 1

    def addAtIndex(self, index, val):
        '''
        在第index插入节点。若index等于链表长度，则在尾部添加，若大于节点长度，则节点不会被插入
        '''
        # 若index等于链表长度，节点添加为尾部
        if index == self.length:
            self.addAtTail(val)
        # 若index==0，节点添加在头部
        elif index == 0:
            self.addAtHead(val)
        # 若index大于链表长度或为负，不插入节点
        elif index + 1 > self.length or index < 0:
            return
        else:
            p = self.head
            # 获得插入位置的前一个节点
            while index > 1:
                index -= 1
                p = p.next
            # 新建当前节点，next指向前一个节点的next
            cur = Node(val, p.next)
            # 前一个节点的next指向当前节点
            p.next = cur
            self.length += 1

    def deleteAtIndex(self, index):
        '''
        删除第index个节点
        '''
        # 若index大于链表长度或为负，不删除节点
        if index + 1 > self.length or index < 0:
            return
        # 若index==0，删除头部节点
        elif index == 0:
            # 重新指定头部节点为当前头部的next
            self.head = self.head.next
            self.length -= 1
            return
        else:
            p = self.head
            # 获得指定位置的前一个节点
            while index > 1:
                p = p.next
                index -= 1
            # 若前一个节点不为倒数第二个节点（也就是删除除头结点、尾节点以外的中间节点）
            if p.next.next is not None:
                p.next = p.next.next
            # 若指定位置的前一个节点为倒数第二个节点（也就是删除尾节点）
            else:
                p.next = None
            self.length -= 1

双指针应用

判断环形链表

给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        '''
        :type head: ListNode
        :rtype: bool
        '''
        '''
        # 方法一 双链表
        p1 = p2 = head
        while p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
            if p1 == p2:
                return True
        return False
        '''
        ### 方法二  哈希表
        if head==None:
            return False
        hash_table=set()
        q=head
        while head:
            if head in hash_table:
                return True
            else:
                hash_table.add(head)  ##set 没有append 只有add
                head=head.next
        return False

环形链表（二）

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。说明：不允许修改给定的链表。

示例一：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例二：

输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例三：

输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        '''
        :type head: ListNode
        :rtype: ListNode
        '''
        p1 = p2 = head
        while p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
            if p1 == p2:
                p = head
                while p != p1:
                    p = p.next
                    p1 = p1.next
                return p
        return None

相交链表

编写一个程序，找到两个单链表相交的起始节点。

示例一：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例二：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例三：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

  • 如果两个链表没有交点，返回 null.
  • 在返回结果后，两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 $O(n)$ 时间复杂度，且仅用 $O(1)$ 内存。
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        '''
        :type head1, head1: ListNode
        :rtype: ListNode
        '''
        '''
        # 方法一 哈希表
        pa, pb = headA, headB
        table = set()
        while pa:
            if pa not in table:
                table.add(pa)
            pa = pa.next
        while pb:
            if pb in table:
                return pb
            pb = pb.next
        return None
        '''
        # 方法二 双指针
        pA = headA
        pB = headB
        while pA != pB:
            pA = pA.next if pA is not None else headB
            pB = pB.next if pB is not None else headA
        return pA

删除链表的导数第N个节点

给定一个链表，删除链表的倒数第 $n$ 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 $n$ 保证是有效的。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        '''
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        '''
        '''
        p = head
        length = 0
        table = []
        while p:
            table.append(p)
            length += 1
            p = p.next
        if n == 1:
            if length == 1:
                return None
            else:
                table[-n-1].next = None
                return head
        if n == length:
            return table[-n+1]
        table[-n-1].next = table[-n-1].next.next
        return head
        '''
        #构建双指针p1与p2，p1先走n步，然后一同运动，当p1指向表尾，p2指向的next即是倒数第N个节点，删除即可。
        dummy = ListNode(0)
        dummy.next = head

        fast = slow = dummy
        for i in range(n):
            fast = fast.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

参考资料

暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
【翻译】The Annotated Diffusion Model

							
							

							
【翻译】Fine-tuning 20B LLMs with RLHF on a 24GB consumer GPU

							
							

							
【翻译】Introducing ⚔️ AI vs. AI ⚔️ a deep reinforcement learning multi-agents competition system

							
							

							
【翻译】Optimum + ONNX Runtime: 为你的Hugging Face模型更容易、更快地训练

							
							

							
Python的30个技巧