注册 登录
编程论坛 C语言论坛

链表逆序问题

飞天大烧卖 发布于 2020-04-15 22:31, 2261 次点击
给定一个单向链表
typedef struct list
{
    int m_data;
    struct list* m_next;
}Link;
写一个函数逆序输出链表;
我的想法比较笨,先遍历一遍链表,把链表里的数存到数组里,在逆向输出数组里的数。
用堆栈怎么处理?用递归又怎么处理?
5 回复
#2
lin51616782020-04-15 23:03
if 空节点 return;
递归 节点->next
输出 节点

完事
#3
rjsp2020-04-15 23:08
单向链表的倒序?那只要交换相邻两个节点的 m_next 就行了。
#4
forever742020-04-15 23:25
显式用栈没啥意思啊,
其实把楼主你的数组从后往前用,再从前往后读,就算是用栈了。
递归也是后台用栈的。
#5
rjsp2020-04-15 23:29
递归的话,链表长则容易爆栈。

程序代码:
#include <stdio.h>

typedef struct node_ {
    int data;
    struct node_* next;
} node;

void list_print( const node* head )
{
    for( ; head; head=head->next )
        printf( "%d%c", head->data, " \n"[head->next==NULL] );
}

node* list_reverse( node* head )
{
    node* pre = NULL;
    for( ; head; )
    {
        node* tmp = head->next;
        head->next = pre;
        pre = head;
        head = tmp;
    }
    return pre;
}

int main( void )
{
    node a[3] = { {0,a+1}, {1,a+2}, {2,NULL} };
   

    node* head = &a[0];
    list_print( head );
   

    head = list_reverse( head );
    list_print( head );
}

#6
fulltimelink2020-04-16 06:18
int,量大可以用位数组。输出时反向处理
_______________
此方式不行,位数组没顺序记录
--------------------------------
刚才大致画了下,可以使用时间换空间的方式:异或
循环期间记录3个值 :
起始值 A
结尾值 B
所有值的异或结果值 C

4   3   6   7   9
  a   b   c   d
    e   f   g
      h   i
         j
a为4和3的异或值 , b为3和6的异或值
当元素个数为奇数时,比如j  ,他的结果就是 4^9
当元素个数为偶数时,比如i, 他的结果就是上层根元素的异或值 也就是  3^6^7^9,
也就是最下面顶点,在元素个数为奇数时为  其值为第一个元素和最后一个元素的异或值, 为偶数时,其值为所有对应根上层元素的异或值

那么通过A  B  C即可计算出  d   c   b   a , 然后结合B 进行异或运算即可倒序计算出   7  6   3 输出即可

todo:代码实现




[此贴子已经被作者于2020-4-16 10:55编辑过]

1