数据结构与算法-链表相关

本篇介绍链表相关的基础题目。

铺垫

python中链表的结构

# 链表结点
class Node:
    def __init__(self, item):
        self.item = item
        self.next = None

题目十

打印两个有序链表的公共部分

题目：给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。

思路：使用外排

代码：

def print_common(h1, h2):
    p1 = h1.head
    p2 = h2.head
    while p1 and p2:  # 边界
        if p1.item < p2.item:
            p1 = p1.next
        elif p1.item > p2.item:
            p2 = p2.next
        else:
            print(p1.item)
            p1 = p1.next
            p2 = p2.next

题目十一

从这个题往后是与链表有关的，链表的优化常常是通过降低空间复杂度来完成的，对于笔试速度优先，不必考虑，对于面试，需要考虑。

判断一个链表是否为回文结构

题目：给定一个链表的头节点head，请判断该链表是否为回文结构。

例如： 1 -> 2 -> 1 返回true ，1 -> 2 -> 2 -> 1 返回true，1 -> 2 -> 3 返回false

思路1：将链表的内容放入栈，然后用出栈的元素，与链表比较，会问结构相同。

代码1：借助栈

# need n extra space
def is_palindrome1(head):
    stack = Stack()
    h1 = head
    while h1:
        stack.put(h1.item)
        h1 = h1.next
    while head:
        if head.item != stack.get():
            return False
        head = head.next
    return True

思路2：一个快指针（一次两个元素），一个慢指针（一次一个元素），这样当快指针到达终点的时候，慢指针位于链表的中央位置，所以，从慢指针位置处开始入栈，然后用入栈的那部分与前半段进行比较。

代码2：快、慢指针

# need n/2 extra space
def is_palindrome2(head):
    stack = Stack()
    right = head  # 快指针
    mid = head  # 慢指针
    while right.next:
        # 快速找到栈的中央（右侧）
        right = right.next.next
        mid = mid.next

    while mid:
        # 右半部分入栈
        stack.put(mid.item)
        mid = mid.next

    while not stack.empty():
        # 链表的左半部分与出栈元素比较
        if head.item != stack.get():
            return False
        head = head.next
    return True

进阶：如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)

---

持续更新中！！！