Reverse Linked List | tech::interview
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
http://www.cnblogs.com/huangxincheng/p/4051854.html
http://segmentfault.com/a/1190000002460482
递归正是压栈和出栈,那么我们就想起来了,这不就是顺序和逆序的关系吗?
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
http://www.cnblogs.com/huangxincheng/p/4051854.html
http://segmentfault.com/a/1190000002460482
递归正是压栈和出栈,那么我们就想起来了,这不就是顺序和逆序的关系吗?
从图中可以看到,当我递归到3再出栈的时候,只需要将6赋给3.next,1赋给6.next,然后这样以此类推
public LinkNode Reverse(LinkNode node)
{
if (node.next == null)
return node;
var prevNode = Reverse(node.next);
var temp = node.next;
temp.next = node;
node.next = null;
return prevNode;
}
第一点:我们在走链表的时候,可以操控的只有两个结点,node和node.next,所以递归出口的时候,一定不能使用最常见的写法。
if (node == null)
return node;
而应该像下面这么写,其实就告诉我们只需要走到6节点就行了,用6.next来判断下是不是链尾,这样做是方便我们进行node和
node.next进行节点交换。
if (node.next == null)
return node;
第二点:当我们每一次出栈的时候,其实也是退到曾今压栈时的方法环境中,进行节点交换的时候,也只能在当前的方法上下文中起效,比如说:出栈到1的时候,其实3和6的节点已经交换了,但是1这个方法环境不知道,它仍然指向6,但此时节点6.next再也不是3了,因为曾今3和6进行了交换,所以这不是我们所期望的,所以在回退的时候,一定要有一个链表保存这个所有节点交换的集合,恰巧在链表中有一个特征就是,只要我有一个指针始终指向头结点的地址,它就相当于一个集合的功能了,因为我不管你后面节点怎么转换,我都可以通过head.next依次找到后面痉挛的所有结点,比如下图中在出栈的过程中,每个出栈的方法环境中都依次交换了node和node.next结点,而我的prevnode始终指向的是结点3,所以我通过3.next就可以找到后面所有的 变化,所以这里就是prevnode的精妙之处。
public LinkNode Reserve(LinkNode node)
{
LinkNode prev = null;
LinkNode next = null;
while (node != null)
{
next = node.next;
node.next = prev;
prev = node;
node = next;
}
return prev;
}
http://algorithmsforever.blogspot.com/2011/11/reversing-linked-list.html
Devise an algorithm to print elements of linked list in reverse without reversing the linked list. State the time and space complexities.
void display_reverse(node *list){
if(list){
display_reverse(list->next);
printf("%d\n", list->info);
}
}
Read full article from Reverse Linked List | tech::interview