剑指Offer面试题5反向打印链表

时间：2021-07-14 14:16:02

面试题5：反向打印链表。

输入一个链表的头结点，从尾到头打印每个节点的值（打印操作一般不改变链表的结构）。

思路1：典型的后进先出，用栈。

思路2：能用栈就能用递归(层数太深容易溢出)，访问到一个节点后，递归输出它后面的节点，再输出该节点自身。

提供了java和c的两种实现。

先看java的：

public class PrintListReversingly {
//尾插法建立链表，传入参数为头结点(头结点本身没有值)
static ListNode createList(ListNode headNode){
ListNode p = headNode;
//确定头结点是否为空
if(p == null){
System.out.println("输入头结点为空，请检查。");
return null;
}else{
Scanner sc = new Scanner(System.in);
System.out.println("输入链表的值，以0结束：");
int n = sc.nextInt();
while(n != 0){
//q为要插入的新节点
ListNode q = new ListNode();
q.data = n;
q.next = null;
p.next = q;
//p始终指向最后一个结点
p = q;
n = sc.nextInt();
}
sc.close();
}
return headNode;
}
//从尾到头打印,用栈。
static void print(ListNode headNode){
Stack<ListNode> stack = new Stack<>();
//这里假设不输出头结点。
while(headNode != null && headNode.next != null){
stack.push(headNode.next);
headNode = headNode.next;
}
while(!stack.isEmpty()){
System.out.println(stack.pop().data);
}
}
public static void main(String[] args) {
ListNode test = new ListNode();
//ListNode test = null;
print(createList(test));
}
}
class ListNode{
int data;
ListNode next = null;
}
//递归方法，仅供参考，返回的arrayList已经是倒序了。
//public ArrayList<Integer> print2(ListNode headNode){
//ArrayList<Integer> arrayList = new ArrayList<>();
//if(headNode != null){
//print2(headNode.next);
//arrayList.add(headNode.data);
//}
//return arrayList;
//}

以下是c实现：

#include<stdlib.h>
#include<stdio.h>

//定义linklist结构体类型
typedef struct linklist
{
    int data;
    linklist* next;
}list,*plist;//建立一个linklist类型的结构体list和一个指向linklist类型的指针plist

//尾插法建链表
void tail_insert(plist* headnode, int num)//如果传入的形参是一个指针p，修改指针指向的内存（也就是*p）会影响实参。
//此时形参headnode是一个二级指针，修改它指向的内存（也就是*headnode，等于实参指针head）就是直接修改实参head。
//还有一种效果相同的方法是：调用时传入实参指针即可，不用传地址了，定义函数形参时，也不用二级指针了，加个&即可。
//如：调用tail_insert(head, number)，定义函数tail_insert(plist &headnode, int num)，函数内可以直接使用headnode。
{
    plist p_new = (plist)malloc(sizeof(list));
    p_new->data = num;          //新元素data设为num
    p_new->next = NULL;         //将新元素next置为空
    plist temp = *headnode;         //每次执行函数时传入的headnode都是不变的，即头结点的地址，所以定义一个可变的指针变量指向头结点
    if (*headnode == NULL)          //头结点为空则赋予p_new为第一个新结点
    {
        *headnode = p_new;
    }
    else                            //若非空
    {
        while (temp->next != NULL)  //temp始终指向尾结点
        {
            temp = temp->next;
        }
        temp->next = p_new;     //将尾结点temp的next设为p_new,即将p_new设为尾结点
    }
}

//反向打印输出链表(递归)
void print_list(plist headnode)
{
    plist elem = headnode;
    if(elem->next!=NULL)
    {
print_list(elem->next);
    }
printf("%d ",elem->data);
    printf("\n");
}

void main()
{
    int number;
    plist head;
    head = NULL;//初始化表头为空

    printf("输入链表值，以-1结束:\n");
    scanf("%d",&number);
    while (number != -1)//输入-1终止输入循环
    {
//为了能在函数内改变外部变量的值，传参时要传递实参的地址，因为head是指针变量所以形参要声明为二级指针。当然这只是一种方法。
        tail_insert(&head, number);
        scanf("%d", &number);
    }

    printf("反向打印输出链表(递归):\n");
    print_list(head);

    system("pause");
}

标签：

相关文章