链表转置算法

Question

给出链表node，如何转置并输出
例如链表node：
node(0)->node(1)->node(2)->node(3)->node(4)
输出结果：
node(4)->node(3)->node(2)->node(1)->node(0)

Answer

**思考步骤：**遍历一次就要形成一个新的转置链表，首先想到的就是链表头插法，头插法逻辑：

1public void addFirst(ListNode newNode,ListNode head) {
2    //链表头插法
3    newNode.next = head;
4    head = newNode;
5}
6

那么梳理一下——
遍历第一次：

1node(0).next = head
2head = node(0);
3

遍历第二次：

1node(1).next = head
2head = node(1);
3

……
遍历最后一次：

1node(4).next = head
2head = node(4);
3

看上去很简单，整个遍历完毕后，就是
node(4)->node(3)->node(2)->node(1)->node(0)结果，但是运行的时候发现不正确，原因很简单，
我们在遍历链表的时候肯定是这么来的

1while(n != null) {
2	//...
3	n = n.next
4}
5

但是我们在上文遍历的情况下，设置了node(x).next = head，这个会导致链表的next指针被修改了，那么n.next肯定指向不了真正的下一个对象

1//有问题的代码
2ListNode pre = null;
3while (n != null) {
4    //头插法
5    n.next = pre;
6    pre = n;
7    n = n.next;   //这里实际上被上文的n.next = pre;覆盖了，导致循环不了！！！
8}
9

所以我们需要定义一个临时变量，保存链表的next内容

1//正确代码
2ListNode pre = null;
3while (n != null) {
4    ListNode t = n.next;   //临时保存next对象
5
6    //头插法
7    n.next = pre;
8    pre = n;
9
10    n = t;   //使用上文临时保存的next对象，保证能够正常迭代
11}
12
13

最后输出的pre就是转置后的链表了

《链表转置算法》 是转载文章，点击查看原文。