登录注册

职位 公司 工资 面试
程序员面试

单链表反转

2011 - 08 - 10 更新
这道题目有两种算法,既然是要反转,那么肯定是要破坏原有的数据结构的:
算法1:我们需要额外的两个变量来存储当前节点curr的下一个节点next、再下一个节点nextnext:
public static Link ReverseLink1(Link head)
{
Link curr = head.Next;
Link next = null;
Link nextnext = null;
//if no elements or only one element exists
if (curr == null || curr.Next == null)
{
return head;
}
//if more than one element
while (curr.Next != null)
{
next = curr.Next; //1
nextnext = next.Next; //2
next.Next = head.Next; //3
head.Next = next; //4
curr.Next = nextnext; //5
}
return head;
}

算法的核心是while循环中的5句话

我们发现,curr始终指向第1个元素。
此外,出于编程的严谨性,还要考虑2种极特殊的情况:没有元素的单链表,以及只有一个元素的单链表,都是不需要反转的。

算法2:自然是递归
如果题目简化为逆序输出这个单链表,那么递归是很简单的,在递归函数之后输出当前元素,这样能确保输出第N个元素语句永远在第N+1个递归函数之后执行,也就是说第N个元素永远在第N+1个元素之后输出,最终我们先输出最后一个元素,然后是倒数第2个、倒数第3个,直到输出第1个:
public static void ReverseLink2(Link head)
{
if (head.Next != null)
{
ReverseLink2(head.Next);
Console.WriteLine(head.Next.Data);
}
}

但是,现实应用中往往不是要求我们逆序输出(不损坏原有的单链表),而是把这个单链表逆序(破坏型)。这就要求我们在递归的时候,还要处理递归后的逻辑。
首先,要把判断单链表有0或1个元素这部分逻辑独立出来,而不需要在递归中每次都比较一次:
public static Link ReverseLink3(Link head)
{
//if no elements or only one element exists
if (head.Next == null || head.Next.Next == null)
return head;
head.Next = ReverseLink(head.Next);
return head;
}

我们观测到:
head.Next = ReverseLink(head.Next);
这句话的意思是为ReverseLink方法生成的逆序链表添加一个空表头。
接下来就是递归的核心算法ReverseLink了:
static Link ReverseLink(Link head)
{
if (head.Next == null)
return head;
Link rHead = ReverseLink(head.Next);
head.Next.Next = head;
head.Next = null;
return rHead;
}

算法的关键就在于递归后的两条语句:
head.Next.Next = head; //1
head.Next = null; //2
啥意思呢?画个图表示就是:

这样,就得到了一个逆序的单链表,我们只用到了1个额外的变量rHead。

您可以返回查看更多面试信息:面试题

热门推荐

热门职位

查看更多