剑指offer6：从 头到尾打印链表

问题

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/solution/mian-shi-ti-06-cong-wei-dao-tou-da-yin-lian-biao-d/

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

实现

递归

• 递推阶段： 每次传入 head.next ，以 head == None（即走过链表尾部节点）为递归终止条件，此时返回空列表 [] 。
• 回溯阶段： 利用 Python 语言特性，递归回溯时每次返回 当前 list + 当前节点值 [head.val] ，即可实现节点的倒序输出。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        return self.reversePrint(head.next) + [head.val] if head else []

• 时间复杂度 O(N) ： 遍历链表，递归 N 次。
• 空间复杂度 O(N) ： 系统递归需要使用 O(N) 的栈空间。

借用栈

题目要求从从尾到头反过来返回每个节点的值，有“后进先出”的特性，故可以考虑使用栈进行实现，特别当链表非常长时，使用递归会导致函数调用的层级很深，从而导致函数调用栈溢出，但是使用栈基于循环实现的代码鲁棒性会更好。

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        stack = []
        while head: # 判断是否到链表的最后
            stack.append(head.val)
            head = head.next
        return stack[::-1]

时间复杂度 O(N)： 入栈和出栈共使用 O(N)时间。
空间复杂度 O(N)： 辅助栈 stack 和数组 res 共使用 O(N) 的额外空间。

测试

# 创建一个链表
node = ListNode(0)
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)

node.next = node1
node1.next = node2
node2.next = node3



s = Solution1()
s.reversePrint(node)

扩展问题

• 找出单向链表中的一个节点，该节点到尾指针的距离为 K。链表的倒数第 0 个结点为链表的尾指针。要求时间复杂度为 O (n)。

链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
}
链表节点的值初始化为 1，2，3，4，5，6，7。

输入描述: 该节点到尾指针的距离K
输出描述: 返回该单向链表的倒数第K个节点，输出节点的值

示例： 输入 2 输出 6

题目地址：https://www.nowcoder.com/practice/0cff324157a24a7a8de3da7934458e34

class Node(object):     
    def __init__(self, val):         
        self.val = val         
        self.next = None              


class Solution(object):
    def __init__(self):
        self.head = None

    def initList(self, data):
        '''
        根据数据依次创建链表
        '''
        self.head = Node(data[0])
        temp = self.head
        for i in data[1:]:
            node = Node(i)
            temp.next = node
            temp = temp.next

    #遍历链表
    def traveList(self):
        result = []
        p = self.head
        while p:
            result.append(p.val)
            p = p.next 
        return result

if __name__ == "__main__":   
    solution = Solution()
    data =  [i for i in range(1, 8)]
    solution.initList(data)
    result = solution.traveList()
    k = int(input())
    print(result[-k])

• 请编写一段代码，实现两个单向有序链表的合并

https://www.nowcoder.com/practice/46bda7f0570a47b6b54a29a0a6ae4c27

1. 解法一：读取两个链表的值，进行排序，排序以后重新构造一个新链表

class Node(object):
    def __init__(self, val):
        self.val = val
        self.next = None



class SinglyLinkedList(object):
    def __init__(self):
        self.head = None

    def initLinkedList(self, data):
        """
        根据列表生成链表
        """
        self.head = Node(data[0])
        temp = self.head
        for i in data[1:]:
            node = Node(i)
            temp.next = node
            temp = temp.next

    def trivelLinkedList(self):
        """
        遍历链表的值
        """
        result = []
        p = self.head
        while p:
            result.append(p.val)
            p = p.next
        return result


if __name__ == "__main__":
    data1 = [int(i) for i in input().split(" ")]
    data2 = [int(i) for i in input().split(" ")]
    linked_list1 = SinglyLinkedList()
    linked_list1.initLinkedList(data1)
    result1 = linked_list1.trivelLinkedList()

    linked_list2 = SinglyLinkedList()
    linked_list2.initLinkedList(data2)
    result2 = linked_list2.trivelLinkedList()
    result = result1 + result2
    result = sorted(result)
    linked_list_result = SinglyLinkedList()
    linked_list_result.initLinkedList(result)
    result = linked_list_result.trivelLinkedList()
    result = [str(i) for i in result]
    print(" ".join(result))

1. 将较短的链表插入到较长的链表中去