[数据结构与算法]数据结构 —— 顺序表和链表

一、顺序表

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