4.从尾到头打印链表

题目描述

从尾到头反过来打印出每个结点的值。

如:
input:

graph LR
1-->2
2-->3

output:

3,2,1

解题思路

1. 递归实现

要实现逆序打印链表 1->2->3;可以使用使用递归,先将链表看做当前节点和右侧节点两部分;如:1->(2->3),先打印右侧节点,再打印当前节点:右侧节点也可以看做两部分如:(2)->(3),也是先打印当前节点的右侧节点,在打印当前节点;如此递归,可实现逆序打印。

代码实现

java 代码
/**
 * 单向链表节点
 * @param <T>
 */
class LinkedNode<T extends Object>{
    private T value;
    private LinkedNode<T> next;

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public LinkedNode<T> getNext() {
        return next;
    }

    public void setNext(LinkedNode<T> next) {
        this.next = next;
    }
}
/**
 * 反向打印链表
 * @param node 链表首节点
 * @return
 */
private ArrayList<Integer> printReverseLink( LinkedNode<Integer> node) {
    ArrayList<Integer>  list = new ArrayList();
    if (node!=null){
        list.addAll(printReverseLink(node.next));
        list.add(node.value);
    }
    return list;
}

public static void main(String[] args){
    LinkedNode<Integer> first = new LinkedNode<>();
    first.setValue(1);
    LinkedNode<Integer> two = new LinkedNode<>();
    two.setValue(2);
    LinkedNode<Integer> three = new LinkedNode<>();
    three.setValue(3);
    two.setNext(three);
    first.setNext(two);
    System.out.println(printReverseLink(first));
}
Kotlin 代码
/**
 * 单向链表节点
 */
data class LinkedNode<T : Any?>(var value: T) {
    var next: LinkedNode<T>? = null
}

/**
 * 反向打印链表
 * @param node 链表首节点
 * @return
 */
private fun printReverseLink(node: LinkedNode<Int>?):ArrayList<Int> {
    val list = ArrayList<Int>()
    if (node!=null){
        list.addAll(printReverseLink(node.next))
        list.add(node.value)
    }
    return list
}
/**
 * 入口函数
 */
fun main(args: Array<String>) {
    val first = LinkedNode(1)
    first.next = LinkedNode(2)
    first.next?.next = LinkedNode(3)
    print(printReverseLink(first))
}

2. 使用头插法

头插法顾名思义是将节点插入到头部:在遍历原始链表时,将当前节点插入新链表的头部,使其成为第一个节点。

链表的操作需要维护后继关系,例如在某个节点 node1 之后插入一个节点 node2,我们可以通过修改后继关系来实现:

node3 = node1.next;
node2.next = node3;
node1.next = node2;

为了能将一个节点插入头部,我们引入了一个叫头结点的辅助节点,该节点不存储值,只是为了方便进行插入操作。不要将头结点与第一个节点混起来,第一个节点是链表中第一个真正存储值的节点。

graph LR
1-->2
2-->3

引入head节点

graph LR
head

循环遍历链接,插入头结点后

node=1

graph LR
head-->1

node=2

graph LR
head-->2
2-->1

node=3

graph LR
head-->3
3-->2
2-->1

代码实现

java 代码
/**
 * 头插法实现反向打印链表
 * 
 * @param node 链表首节点
 * @return
 */
private ArrayList<Integer> printReverseLinkToHead(LinkedNode<Integer> node) {
    LinkedNode<Integer> head = new LinkedNode<>();
    head.setValue(-1);
    while (node != null) {
        LinkedNode<Integer> next = node.getNext();
        node.setNext(head.getNext());
        head.setNext(node);
        node = next;
    }
    ArrayList<Integer> list = new ArrayList();
    head = head.getNext();
    while (head != null) {
        list.add(head.getValue());
        head = head.getNext();
    }
    return list;
}

public static void main(String[] args){
    LinkedNode<Integer> first = new LinkedNode<>();
    first.setValue(1);
    LinkedNode<Integer> two = new LinkedNode<>();
    two.setValue(2);
    LinkedNode<Integer> three = new LinkedNode<>();
    three.setValue(3);
    two.setNext(three);
    first.setNext(two);
    
    System.out.println(printReverseLinkToHead(first));
}
Kotlin 代码
/**
 * 使用头插法反向打印链表
 * @param node 链表首节点
 * @return
 */
private fun printReverseLinkToHead(node: LinkedNode<Int>?):ArrayList<Int> {
    var currentNode = node
    var head:LinkedNode<Int>? = LinkedNode(-1)
    while (currentNode!=null){
        val next = currentNode.next
        currentNode?.next = head!!.next
        head!!.next = currentNode
        currentNode = next
    }
    val list = ArrayList<Int>()
    head = head!!.next
    while (head!=null){
        list.add(head.value)
        head = head.next
    }
    return list
}

/**
 * 入口函数
 */
fun main(args: Array<String>) {
    val first = ListNode(1)
    first.next = ListNode(2)
    first.next?.next = ListNode(3)
    print(printReverseLinkToHead(first))
}

3. 使用栈来实现

栈的规则时后进先出,则可以将链表遍历存放到栈中,然后在出栈则出栈顺序就是反向打印链表

代码实现

java 代码
/**
 * 使用栈实现反向打印链表
 *
 * @param node 链表首节点
 * @return
 */
private ArrayList<Integer> printReverseLinkToHeadWithStack(LinkedNode<Integer> node){
    Stack<Integer> stack = new Stack<>();
    while (node != null) {
        stack.add(node.getValue());
        node = node.next;
    }
    ArrayList<Integer> list = new ArrayList();
    while (!stack.isEmpty()) {
        list.add(stack.pop());
    }
    return list;
}

public static void main(String[] args){
    LinkedNode<Integer> first = new LinkedNode<>();
    first.setValue(1);
    LinkedNode<Integer> two = new LinkedNode<>();
    two.setValue(2);
    LinkedNode<Integer> three = new LinkedNode<>();
    three.setValue(3);
    two.setNext(three);
    first.setNext(two);
    
    System.out.println(printReverseLinkToHeadWithStack(first));
}
Kotlin 代码
/**
 * 使用栈反向打印链表
 * @param node 链表首节点
 * @return
 */
private fun printReverseLinkToHeadWithStack(node: LinkedNode<Int>?): ArrayList<Int> {
    val stack = Stack<Int>()
    var current = node
    while (current != null) {
        stack.push(current.value)
        current = current.next
    }
    val list = ArrayList<Int>()
    while (!stack.empty()) {
        list.add(stack.pop())
    }
    return list
}

/**
 * 入口函数
 */
fun main(args: Array<String>) {
    val first = ListNode(1)
    first.next = ListNode(2)
    first.next?.next = ListNode(3)
    print(printReverseLinkToHeadWithStack(first))
}

引用声明

该题目引用自
牛客网