题目描述:
解题思路:
关于单链表的反转有迭代和递归两种方法,方法不在多,本文主要介绍迭代的方法。
迭代的方法,要使用三个指针,需要注意一点的是指针的初始化,对第一个指针初始化为pre=null,第二个指针初始化为current=head,第三个指针初始化为next=null,不能将第一个指针pre初始化成head,否则最后反转后的链表的尾端指向的不是null。
下面以单链表1->3->5->7举例:
(1)初始情况:
(2)执行迭代操作:
①:next=current.next;//用next保存current的下一个节点
②:current.next=pre;//将指向当前节点的current的下一个节点指向pre(表示前一个节点)
③:pre=current;//将pre指针指向current所指的节点
④:current=next;//将current指针指向next所指的节点,即把current向前移动
第一轮操作结束后:
(3)第二轮迭代操作后:
(4)最终结果:
Java代码:
1 //public class LeetCode206为测试 2 public class LeetCode206 { 3 public static void main(String[] args) { 4 ListNode n1=new ListNode(1),n2=new ListNode(3),n3=new ListNode(5),n4=new ListNode(7); 5 n1.next=n2; 6 n2.next=n3; 7 n3.next=n4; 8 System.out.println("原来链表:"+n1.val+"->"+n2.val+"->"+n3.val+"->"+n4.val); 9 ListNode n=new Solution().reverseList(n1); 10 System.out.println("反转链表:"+n.val+"->"+n.next.val+"->"+n.next.next.val+"->"+n.next.next.next.val); 11 } 12 } 13 class Solution { 14 public ListNode reverseList(ListNode head) { 15 ListNode pre=null; 16 ListNode current=head; 17 ListNode next=null; 18 while(current!=null){ 19 next=current.next; 20 current.next=pre; 21 pre=current; 22 current=next; 23 } 24 return pre; 25 } 26 } 27 class ListNode { 28 int val; 29 ListNode next; 30 ListNode(int x) { val = x; } 31 }
程序结果: