链表的翻转

文章目录

1. 1. 题目
2. 2. 解题
3. 3. 代码
4. 4. 参考

题目

将链表1->2->3->4翻转成4->3->2->1。

解题

最简单就是遍历链表，然后保存到一个数组中，然后再向后构建数组，当然，这种方式不好，会有额外开销。-_-
这里来介绍一下另一种方法：
假设现在的链表是

null->1->2->3->4->null

如果我们想办法将2移到1的前面，然后3又移到2的前面，最后将4移动3的前面，这不就完了嘛？
好，现在开始移动：

    2
   / \ 
null  1->3->4->null
将1指向2的next，然后将2的next指向head的next，然后head的next指向2

    3-2
   /  |
null  1->4->null
然后再移动3

    4-3-2
   /    |
null    1->null
再移动4

这种方式就不需要额外的空间，也只需要遍历一遍即可。

代码

具体的代码如下，链表节点的数据结构为

static class Node{
	public int val;
	public Node next;
	
	public Node(int val,Node next)	{
	
		this.val=val;
		this.next=next;
	}
}

则其翻转的函数为：

public static void revert(Node head){

	Node temp=head.next;
	Node p=null;
	while(temp.next!=null)
	{
		p=temp.next;//保存1号的下一个节点
		temp.next=p.next;//将1号的下一个节点删除
		p.next=head.next;//将1号的下一个节点指向链表第一点节点（非头部）
		head.next=p;//更新头部的指向
	}
}

测试的代码为：

public static void main(String[] args) {
	// TODO Auto-generated method stub
	Node node4=new Node(4,null);
	Node node3=new Node(3,node4);
	Node node2=new Node(2,node3);
	Node node1=new Node(1,node2);
	Node head=new Node(-1,node1);
	print(head);
	revert(head);
	print(head);
	
}

最终的输出为

1,2,3,4,
4,3,2,1,

参考

1. http://blog.csdn.net/chuyuqing/article/details/44457665

---

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权