黑马程序员技术交流社区

标题: Python数据结构学习小结之LinkedList：单链表结构 [打印本页]

作者: qjm 时间: 2019-3-28 23:54
标题: Python数据结构学习小结之LinkedList：单链表结构
本帖最后由 qjm 于 2019-3-29 01:18 编辑

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

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

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2