一、 链表的基本操作

• 本题考察链表的基本操作：打印链表所有元素，查询指定位置的样本，插入指定位置样本，和删除指定位置样本；
• 输入：输入数据只有一组，第一行有n+1个整数，第一个整数是这行余下的整数数目n，后面是n个整数。
  这一行整数是用来初始化列表的，并且输入的顺序与列表中的顺序相反，也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。第二行有一个整数m，代表下面还有m行。每行有一个字符串，字符串是“get”，“insert”，“delete”，“show”中的一种。如果是“get”，代表获得第a个元素。（a从1开始计数）；如果是“delete”，代表删除第a个元素。（a从1开始计数）；如果是“insert”，则其后跟着两个整数a和e，代表在第a个位置前面插入e。（a从1开始计数） ；“show”之后没有正数，直接打印链表全部内容。
• 输出：如果获取成功，则输出该元素；如果删除成功，则输出“delete OK”；如果获取失败，则输出“get fail”；
  如果删除失败，则输出“delete fail”；如果插入成功，则输出“insert OK”，否则输出“insert fail”；如果是“show”，则输出列表中的所有元素；如果列表是空的，则输出“Link list is empty”。注：所有的双引号均不输出。
• 样例输入：
  3 3 2 1
  21
  show
  delete 1
  show
  delete 2
  show
  delete 1
  show
  delete 2
  insert 2 5
  show
  insert 1 5
  show
  insert 1 7
  show
  insert 2 5
  show
  insert 3 6
  show
  insert 1 8
  show
  get 2

解题思路：

注意插入删除位置的判断，然后是移位保持正确。

#定义链表节点
class LinkedNode:
    def __init__(self, val = 0, next = None):
        self.val = val
        self.next = next

#定义链表基本操作
class MyLinkedList:
    def __init__(self):
        self._size = 0
        self._dummyHead = LinkedNode(0)
    #获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点 
    def get(self, index):
        if index > (self._size - 1) or index < 0:
            return -1
        cur = self._dummyHead.next
        while index:
            cur = cur.next
            index -= 1
        return cur.val
    #在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
    def addAtHead(self, val):
        newNode = LinkedNode(val)
        newNode.next = self._dummyHead.next
        self._dummyHead.next = newNode
        self._size += 1
    #在链表最后面添加一个节点
    def addAtTail(self, val):
        newNode = LinkedNode(val)
        cur = self._dummyHead
        while cur.next:
            cur = cur.next
        cur.next = newNode
        self._size += 1
    #在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    def addAtIndex(self, index, val):
        if index > self._size:
            return -1
        if index < 0:
            return -1
        newNode = LinkedNode(val)
        cur = self._dummyHead
        while index:
            cur = cur.next
            index -= 1
        newNode.next = cur.next
        cur.next = newNode
        self._size += 1
        return 0
    #删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
    def deleteAtIndex(self, index):
        if index >= self._size or index < 0:
            return -1
        cur = self._dummyHead
        while index:
            cur = cur.next
            index -= 1
        tmp = cur.next
        cur.next = cur.next.next
        del tmp
        self._size -= 1
        return 0
    #打印链表
    def printLinkedList(self):
        cur = self._dummyHead
        if cur.next == None:
            return -1
        while cur.next:
            print(cur.next.val, end = ' ')
            cur = cur.next
        print()
        return 0

if __name__ == "__main__":
    while True:
        mylinklist = MyLinkedList()
        try:
            # 读取链表长度和链表数值
            n, *nums = list(map(int, input().split()))
            # 初始化链表
            for i in range(n):
                mylinklist.addAtHead(nums[i])
            # 读取操作的个数
            m = int(input())
            for i in range(m):
                s = input().split()
                if s[0] == "show":
                    if mylinklist.printLinkedList() == -1:
                        print("Link list is empty")
                if s[0] == "delete":
                    t = int(s[1])
                    if mylinklist.deleteAtIndex(t - 1) == -1:
                        print("delete fail")
                    else:
                        print("delete OK")
                if s[0] == "insert":
                    t = int(s[1])
                    z = int(s[2])
                    if mylinklist.addAtIndex(t - 1, z) == -1:
                        print("insert fail")
                    else:
                        print("insert OK")
                if s[0] == "get":
                    t = int(s[1])
                    getValue = mylinklist.get(t - 1)
                    if getValue == -1:
                        print("get fail")
                    else:
                        print(getValue)
        except:
            break

二、单链表反转

• 题目表述：根据一个整数序列构造一个单链表，然后将其反转。例如：原单链表为 2 3 4 5 ，反转之后为5 4 3 2
• 输入：输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开。
• 输出： 针对每组测试数据，输出包括两行，分别是反转前和反转后的链表元素，用空格隔开。如果链表为空，则只输出一行，list is empty。
• 样例输入：
  5 1 2 3 4 5
  0

解题思路

单链表反转其实就是将链表中当前元素的指针指向前一个元素；中间需要使用temp保存当前元素以保证能够访问链表中下一个元素，以此迭代下去。

class LinkNode:
    def __init__(self, val, next=None) -> None:
        self.val = val
        self.next = next


def printLinkList(node):
    while node.next:
        print(node.val, end=" ")
        node = node.next
    print(node.val)


def reverseLinkList(node):
    pre = None
    cur = node
    temp = None
    while cur:
        temp = cur.next
        cur.next = pre  # 翻转操作
        pre = cur  # 更新pre 和 cur指针
        cur = temp
    return pre

if __name__ == "__main__":
    while True:
        try:
            # 输入5 1 2 3 4 5，表示链表有5个节点，值分别为1 2 3 4 5
            n, *nums = map(int, input().split())
        except:
            break
        if n == 0:
            print("list is empty")
            continue
        dummyHead = LinkNode(0)  # 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        cur = dummyHead
        for i in range(n):  # 开始构造节点
            cur.next = LinkNode(nums[i])
            cur = cur.next
        printLinkList(dummyHead.next)  # 打印链表
        printLinkList(reverseLinkList(dummyHead.next))  # 打印翻转后的链表

三、删除链表中的重复元素

• 题目描述：根据一个递增的整数序列构造有序单链表，删除其中的重复元素
• 输入：输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开
• 输出：针对每组测试数据，输出包括两行，分别是删除前和删除后的链表元素，用空格隔开。如果链表为空，则只输出一行，list is empty。

解题思路

链表中连续两个节点的值相等，则前一个节点的指针指向下下个节点，再接着判断。

class LinkNode:
    def __init__(self, val, next=None) -> None:
        self.val = val
        self.next = next

def printLinkList(node): # 打印当前链表
    while node.next:
        print(node.val, end=" ")
        node = node.next
    print(node.val)

def removeSame(head):
    if not head:
        return None
    cur = head
    while cur and cur.next:
        if cur.val == cur.next.val: # 如果当前元素和下一个元素值相等
            cur.next = cur.next.next # 当前元素的指针跳过下一个元素，指向下下个。
        else:
            cur = cur.next
    return head

if __name__ == "__main__":
    while True:
        try:
            n, *nums = map(int, input().split())
        except:
            break
        if n == 0:
            print("list is empty")
            continue
        dummyHead = LinkNode(0)  # 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        cur = dummyHead
        for i in range(n):  # 开始构造节点
            cur.next = LinkNode(nums[i])
            cur = cur.next
        printLinkList(dummyHead.next)  # 打印链表
        printLinkList(removeSame(dummyHead.next))  # 打印去重后的链表