Python数据结构学习小结之LinkedList：单链表结构

目录

1.链表的基础知识

1.1 链表的基本结构

1.2 单链表的节点

2.单链表的基本操作

2.1 单链表的遍历

2.2 单链表的增删改查

3. Leetcode单链表相关题目解答分享

参考：https://blog.csdn.net/qq_39422642/article/details/78988976

1.链表的基础知识

1.1链表的基本结构

链表是通过一个个节点组成的，每个节点有两个部分，左边部分称为值域，用来存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。它能保持数据之间的逻辑顺序，但存储空间不必按照顺序存储。因此，对于链表的插入和删除操作速度非常快，其时间复杂度和空间复杂度均为O（1），这也是链表结构的最大特点。

链表可以分为单向链表和单向循环链表，双向链表和双向循环链表，如图为单向链表和单向循环链表：

由于个人知识有限，在这仅介绍和总结单向链表的相关知识。在单向链表中，链表的头节点一般命名为head，是链表的第一个节点，没有指针指向它，链表的尾节点一般命名为tail，它的指针指向空值None。

1.2 单链表的节点

       在Python中，单链表节点可作如下定义：

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

2．单链表的基本操作

2.1 单链表的遍历

head为头节点，val为节点保存的值，next为节点指针指向的下一个节点,代码如下：

while head:
    print(head.val)
    head = head.next

2.2 单链表的增删改查

2.2.1 单链表的增加元素

       从前插入:

1.若被插入数据为空，返回原来的头节点

2.使用该输入数据创建一个节点，并将该节点指向原来头节点

3.设置该节点为头节点

该操作的时间复杂度和空间复杂度均为O(1)

def preInsert(head, data):      if data == None:        
    return head   
  node = ListNode(data)   
  node.next = head   
    return node

从后插入：

1.若输入数据为空，返回原来的头节点

2.若头节点为空，直接将输入数据作为头节点

3.遍历整个链表，直到当前节点的下一个节点为None时，达到尾节点，将当前节点的下一个节点设置为输入数据

该操作的时间复杂度为O(n)（需要遍历链表），空间O(1)

def postInsert(head, data):   
  if data == None:        
    return head   
  node = head   
  while node.next:        
    node = node.next   
    node.next = ListNode(data)   
  return head

2.2.2 单链表的查找元素

1.若查找的数据为空，返回

2.设置头节点为当前节点，若当前节点不为None,遍历整个链表

3.若当前节点的val与输入的val相同，返回当前节点，否则继续查找下一个节点直至链表链表尾节点。

该操作的时间复杂度为O(n),空间复杂度为O(1).

def search(head, target_val):   
  if target_val == None:        
    return head   
  node = head   
  while node:        
    if node.val == target_val:            
      return node        
    node = node.next   
  return head

2.2.3 单链表的修改元素

其原理与查找相同，只是在找到后将目标节点原来存储的值修改为新值，不赘述，代码如下：

def modify(head, old_val, new_val):   
  node = head   
  while node:        
    if node.val == old_val:            
      node.val = new_val            
      return head        
    node = node.next   
  return head

2.2.4 单链表的删除元素

       1.判断头节点的值是否是需要删除的元素，若是，直接将头节点的next指针设为空，并返回头节点的下一个节点。

       2.遍历链表，如果找到存储待删除元素的节点，则将该节点的前一个节点的next指针指向该节点的后一个节点，从而这节点就从链表中删除了。

该操作的时间复杂度为O(n),空间复杂度为O(1).

def delete(head, val):      if val == None:        
    return head   
  if head.val == val:        
    node = head.next        
    head.next = None        
    return node   
  node = head   
  while node.next:        
    if node.next.val == val:            
      node.next = node.next.next            
      return head        
    node = node.next   
  return head      

3. Leetcode单链表相关题目解答分享

第2题 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807# Definition for singly-linked list.# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):   
    def addTwoNumbers(self, l1, l2):        
    """        
    :type l1: ListNode      
     :type l2: ListNode      
     :rtype: ListNode        
    """        
    head1=l1        
    head2=l2        
    root =n= ListNode(0)        
    carry=0        
    while head1 or head2 or carry:            
        val1 = val2 = 0            
        if head1:               
            val1 = head1.val               
            head1=head1.next            
        if head2:               
            val2 = head2.val               
            head2=head2.next            
        carry,val = divmod(val1+val2+carry,10)           
        n.next=ListNode(val)            
        n=n.next        
    return  root.next


第19题：删除链表的倒数第N个节点

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.
解题思路：通过使用fast和slow两个指针，可以实现一次遍历就完成所要求的的功能，提高效率。
# 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        
"""        
        if not head.next:            
            return        
    slow = fast = head        
    for i in range(n):            
        fast = fast.next        
    if not fast:            
        head = head.next            
        return head        
    while fast.next:            
        fast = fast.next            
        slow = slow.next        
        slow.next = slow.next.next        
    return head

第61题：旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:向右旋转 1 步: 5->1->2->3->4->NULL
     向右旋转 2 步: 4->5->1->2->3->NULL
# Definition for singly-linked list.# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):   
    def rotateRight(self, head, k):        
    """        
    :type head: ListNode        
    :type k: int        
    :rtype: ListNode        
    """        
    if not head:            
        return        
    step = 0        
    node = head      
    while node.next:            
        node = node.next            
        step += 1        
    length = step + 1        
    k = k % length        
    if k == 0:            
        return head        
    node = head        
    for i in range(k):            
        node = node.next        
        fast = node        
        slow = head        
    while fast.next:            
        fast = fast.next            
        slow = slow.next        
    fast.next = head        
    head = slow.next        
    slow.next = None        
    return head

个人能力原因，后续其它题目没有完成或者不会做。欢迎联系联系交流。再次感谢链接所示文章提供的参考，如有侵权，联系删除。如需转载，请标明出处。

Python数据结构学习小结之LinkedList：单链表结构

目录

1.链表的基础知识

1.1 链表的基本结构

1.2 单链表的节点

2.单链表的基本操作

2.1 单链表的遍历

2.2 单链表的增删改查

3. Leetcode单链表相关题目解答分享

参考：https://blog.csdn.net/qq_39422642/article/details/78988976

1.链表的基础知识

1.1链表的基本结构

链表是通过一个个节点组成的，每个节点有两个部分，左边部分称为值域，用来存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。它能保持数据之间的逻辑顺序，但存储空间不必按照顺序存储。因此，对于链表的插入和删除操作速度非常快，其时间复杂度和空间复杂度均为O（1），这也是链表结构的最大特点。

链表可以分为单向链表和单向循环链表，双向链表和双向循环链表，如图为单向链表和单向循环链表：

由于个人知识有限，在这仅介绍和总结单向链表的相关知识。在单向链表中，链表的头节点一般命名为head，是链表的第一个节点，没有指针指向它，链表的尾节点一般命名为tail，它的指针指向空值None。

1.2 单链表的节点

       在Python中，单链表节点可作如下定义：

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

2．单链表的基本操作

2.1 单链表的遍历

head为头节点，val为节点保存的值，next为节点指针指向的下一个节点,代码如下：

while head:
    print(head.val)
    head = head.next

2.2 单链表的增删改查

2.2.1 单链表的增加元素

       从前插入:

1.若被插入数据为空，返回原来的头节点

2.使用该输入数据创建一个节点，并将该节点指向原来头节点

3.设置该节点为头节点

该操作的时间复杂度和空间复杂度均为O(1)

def preInsert(head, data):      if data == None:        
    return head   
  node = ListNode(data)   
  node.next = head   
    return node

从后插入：

1.若输入数据为空，返回原来的头节点

2.若头节点为空，直接将输入数据作为头节点

3.遍历整个链表，直到当前节点的下一个节点为None时，达到尾节点，将当前节点的下一个节点设置为输入数据

该操作的时间复杂度为O(n)（需要遍历链表），空间O(1)

def postInsert(head, data):   
  if data == None:        
    return head   
  node = head   
  while node.next:        
    node = node.next   
    node.next = ListNode(data)   
  return head

2.2.2 单链表的查找元素

1.若查找的数据为空，返回

2.设置头节点为当前节点，若当前节点不为None,遍历整个链表

3.若当前节点的val与输入的val相同，返回当前节点，否则继续查找下一个节点直至链表链表尾节点。

该操作的时间复杂度为O(n),空间复杂度为O(1).

def search(head, target_val):   
  if target_val == None:        
    return head   
  node = head   
  while node:        
    if node.val == target_val:            
      return node        
    node = node.next   
  return head

2.2.3 单链表的修改元素

其原理与查找相同，只是在找到后将目标节点原来存储的值修改为新值，不赘述，代码如下：

def modify(head, old_val, new_val):   
  node = head   
  while node:        
    if node.val == old_val:            
      node.val = new_val            
      return head        
    node = node.next   
  return head

2.2.4 单链表的删除元素

       1.判断头节点的值是否是需要删除的元素，若是，直接将头节点的next指针设为空，并返回头节点的下一个节点。

       2.遍历链表，如果找到存储待删除元素的节点，则将该节点的前一个节点的next指针指向该节点的后一个节点，从而这节点就从链表中删除了。

该操作的时间复杂度为O(n),空间复杂度为O(1).

def delete(head, val):      if val == None:        
    return head   
  if head.val == val:        
    node = head.next        
    head.next = None        
    return node   
  node = head   
  while node.next:        
    if node.next.val == val:            
      node.next = node.next.next            
      return head        
    node = node.next   
  return head      

3. Leetcode单链表相关题目解答分享

第2题 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807# Definition for singly-linked list.# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):   
    def addTwoNumbers(self, l1, l2):        
    """        
    :type l1: ListNode      
     :type l2: ListNode      
     :rtype: ListNode        
    """        
    head1=l1        
    head2=l2        
    root =n= ListNode(0)        
    carry=0        
    while head1 or head2 or carry:            
        val1 = val2 = 0            
        if head1:               
            val1 = head1.val               
            head1=head1.next            
        if head2:               
            val2 = head2.val               
            head2=head2.next            
        carry,val = divmod(val1+val2+carry,10)           
        n.next=ListNode(val)            
        n=n.next        
    return  root.next


第19题：删除链表的倒数第N个节点

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.
解题思路：通过使用fast和slow两个指针，可以实现一次遍历就完成所要求的的功能，提高效率。
# 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        
"""        
        if not head.next:            
            return        
    slow = fast = head        
    for i in range(n):            
        fast = fast.next        
    if not fast:            
        head = head.next            
        return head        
    while fast.next:            
        fast = fast.next            
        slow = slow.next        
        slow.next = slow.next.next        
    return head

第61题：旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:向右旋转 1 步: 5->1->2->3->4->NULL
     向右旋转 2 步: 4->5->1->2->3->NULL
# Definition for singly-linked list.# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):   
    def rotateRight(self, head, k):        
    """        
    :type head: ListNode        
    :type k: int        
    :rtype: ListNode        
    """        
    if not head:            
        return        
    step = 0        
    node = head      
    while node.next:            
        node = node.next            
        step += 1        
    length = step + 1        
    k = k % length        
    if k == 0:            
        return head        
    node = head        
    for i in range(k):            
        node = node.next        
        fast = node        
        slow = head        
    while fast.next:            
        fast = fast.next            
        slow = slow.next        
    fast.next = head        
    head = slow.next        
    slow.next = None        
    return head

个人能力原因，后续其它题目没有完成或者不会做。欢迎联系联系交流。再次感谢链接所示文章提供的参考，如有侵权，联系删除。如需转载，请标明出处。