offer第6题 从头到尾打印链表

该系列文章为本人刷leetcode的记录,主要旨在分享刷题的思路及算法解析(尽可能的一题多解),另方便自己日后查阅回顾。代码的实现语言是python和go。

想进大厂免不了刷题,一起加油吧，小伙伴们!

链接: https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

从头到尾打印链表

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

示例 1：

 输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

分析:链表和二叉树的问题都可以先想到递归解法；本题实际上就是实现对列表的倒序输出。

解法:

1. 递归
2. 遍历:按照正序遍历添加,最后再反转一下

注意*:如果返回的不是数组,也是链表。则需要使用双指针。

def reversePrint(head: ListNode) :
    #if head == None: return None
    #方法1:递归
    # reverse_list = reversePrint(head.next) + [head.val] if head else []
    # return reverse_list

    """"
    #方法1拓展:递归;如果返回的不是数组而是链表
    # if not head or not head.next: return head

    # ret = reversePrint(head.next)
    # head.next.next = head  #
    # head.next = None

    # return ret

    #方法1拓展:递归;如果返回的不是数组而是链表;使用内部定义的递归函数
    #以下的双指针解法做参考。递归时目前难想到
    # def recur(cur,pre):
    #     if not cur: return pre
    #     ret = recur(cur.next,cur)
    #     cur.next = pre
    #
    #
    #     return ret
    #
    # return recur(head,None)

    #以下的解法容易想到点.套用递归公式.
    #使用递归公式f(n)=f(n-1)+? 则recur(head.next)就是f(n-1);只需要解决以node=head为节点的需要解决的局部问题即可.
    def recur(head):
        if not head or not head.next: return head
        ret = recur(head.next)
        head.next.next = head
        head.next = None

        return ret

    return recur(head)
    """




    #方法2:遍历;首尾双指针;
    pre,cur = None,head
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp

    reverse_head = []
    while pre:
        reverse_head.append(pre.val)
        pre = pre.next



    return reverse_head

package main

import "fmt"


type ListNode struct {
	Val int
	Next *ListNode
}
func reversePrint(head *ListNode) []int {

	//方法1:递归
	//链表,二叉树的问题都可以想到递归
	//return append(reversePrint(head.Next),head.Val)

	//if head==nil {return nil}
	//
	reverse_head :=[]int{}
	//reverse_head  := append(reversePrint(head.Next),head.Val)
	//
	//return reverse_head


	//方法1拓展:如果返回的是倒序的链表;
	使用递归公式;f(n)=f(n-1)+?
	//var recur func(head *ListNode) *ListNode
	//
	//recur = func(head *ListNode) *ListNode{
	//	//递归终止条件
	//	if head==nil || head.Next==nil{return head}
	//
	//	//递归公式
	//	ret := recur(head.Next)
	//	head.Next.Next = head
	//	head.Next = nil
	//
	//	return ret
	//
	//}

	//return recur(head)

	//方法2:顺序遍历;
	//先构建一个倒序的链表;再遍历链表存值.
	//if head==nil{return nil}
	//
	//var pre *ListNode
	//cur := head
	//for cur != nil{
	//	//链表更改指向需要借用双指针
	//	//这里只需要将cur.Next 指向 pre即可;然后分别移动cur和pre往下走一格
	//	tmp:= cur.Next
	//	cur.Next = pre
	//	pre = cur
	//	cur = tmp
	//
	//}
	//
	//
	//reverse_head :=make([]int,0)
	//
	//for pre!=nil{
	//	reverse_head = append(reverse_head,pre.Val)
	//	pre = pre.Next
	//}
	//
	//return reverse_head

	//方法3:直接构造一个新链表
	cur,other := head,head

	values := []int{}

	for cur!=nil{
		values = append(values,cur.Val)
		cur = cur.Next

	}

	n := len(values)-1
	for ;n>=0;n--{
		other.Val = values[n]
		other = other.Next
	}


	for head !=nil{
		fmt.Println(head.Val)
		head = head.Next
	}

	return values


}

链表、二叉树的问题首先要想到递归;其次,递归算法的空间复杂度一般都比较高(会调用n个栈);
所以使用常规的遍历有时候使用效果反而更好(针对链表的题一般遍历都需要双指针及以上);