一、顺序表
1、长度为 n 的顺序表 L，编写一个时间复杂度为 O(n)，空间复杂度为O(1) 的算法，该算法删除线性表中所有值为 x 的数据元素。?
方法一：定义指针 index，遍历数组的元素，当元素的值不为 x 时，将当前元素前置到 index 位置上，同时 index 自增。
def function(nums, x):
index = 0
for i in range(0, len(nums)):
if nums[i] != x:
nums[index] = nums[i]
index += 1
print(nums[0: index])
方法二：定义变量 count，用于统计值为 x 的数量，遍历数组的元素，当元素的值不为 x，将下标为 i 的元素前置到 i - count 的位置。
def function(nums, x):
count = 0
for i in range(0, len(nums)):
if nums[i] == x:
count += 1
else:
nums[i - count] = nums[i]
print(nums[0: len(nums) - count])
2、从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同
思路：定义指针 index，遍历数组的元素，当元素 nums[index] 不等于 nums[i] 时，说明 nums[index] 不需要被删除，所以，index 先自增，然后，将当前元素前置到 index 位置上。
举例说明：
def function(nums):
index = 0
for i in range(1, len(nums)):
if nums[index] != nums[i]:
index += 1
nums[index] = nums[i]
print(nums[0: index + 1])
二、链表
引入头结点后，第一个结点的位置被存放在头结点的指针域中，有点如下：
- 在链表中的第一个位置和其他位置上的结点操作一致，无须进行特殊处理；
- 空链表和非空链表的处理一致。
尾插法建表
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def create_link_list(nums):
head = ListNode(0)
pointer = head
for i in nums:
temp = ListNode(i)
pointer.next = temp
pointer = pointer.next
return head
create_link_list([1, 2, 3, 4, 5])
遍历链表
def print_link(head):
pointer = head.next
while pointer is not None:
print(pointer.val)
pointer = pointer.next
1、头插法实现单链表反转或者就地逆置单链表
def function(head):
pointer = head.next
p_index = ListNode(0)
head = ListNode(0)
while pointer is not None:
p_index = pointer
pointer = pointer.next
p_index.next = head.next
head.next = p_index
2、设 head 为带头结点的单链表，编写算法实现从尾到头反向输出每个节点的值
def function(head): # head 链表参照尾插法自己创建，输入列表，输出链表
stack = Stack() # Stack 是作者基于列表封装的类，实现了栈的功能
pointer = head.next
while pointer is not None:
stack.push(pointer.val)
pointer = pointer.next
while not stack.is_empty():
print(stack.pop())
3、有一个带头结点的单链表 head，涉及一个算法使其元素递增有序。
思路：插入排序法实现链表的排序
def function(head):
pointer = head.next
head = ListNode(0)
while pointer is not None:
p_index = pointer
pointer = pointer.next
temp_index = head
while temp_index.next is not None and temp_index.next.val < p_index.val:
temp_index = temp_index.next
p_index.next = temp_index.next
temp_index.next = p_index
4、给定两个单链表，编写算法找出两个链表的公共结点。
思路：如果链表有公共结点，那么，两个链表从公共结点到尾结点一定是相同的，所以，先将其中较长的链表遍历至和较短的链表相同长度，然后，同时遍历并判断当前两个链表的结点是否相同。
def getIntersectionNode(headA, headB):
countA = 0
countB = 0
index_A = headA
while index_A is not None:
countA += 1
index_A = index_A.next
index_B = headB
while index_B is not None:
countB += 1
index_B = index_B.next
distance = 0
long_link = ListNode(0)
short_link = ListNode(0)
if countA - countB > 0:
distance = countA - countB
long_link = headA
short_link = headB
else:
distance = countB - countA
long_link = headB
short_link = headA
for i in range(0, distance):
long_link = long_link.next
while long_link is not None:
if long_link == short_link:
return long_link
long_link = long_link.next
short_link = short_link.next
return None
|