java单链表倒转
fb0122 人气:0java中有关单链表反转的方法有很多种，这里记录一种并附上详细步骤：
代码如下
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre;
ListNode temp;
pre = head; // 前驱节点
ListNode cur = head.next //当前节点
while(cur != null && cur.next != null){
temp = cur.next; //(1)
cur.next = pre; //(2)
pre = cur; //(3)
cur = temp; //(4)
}
head.next = null //原头节点，反转后尾节点
return pre; //原尾节点 反转后头节点
}
}主要的操作是在while循环中，下面画图解释一下是如何实现单链表倒转的：
首先java中没有指针的概念，但是可以看到ListNode中的next属性其实就代表指向下一个节点的“指针”，因此可以这样来理解：
1、原单链表：
假设单链表有三个元素[1,2,3]，0为上述的头对象
2、执行（1）、（2）后：
cur.next指向了n.next:
3、执行(3):
4、执行（4）：
第一次循环结束，第一次循环后的单链表如上图所示。
cur != null && cur.next != null，因此执行第二次循环：
5、第二次执行（1），（2）：
6、第二次执行（3）：
7、第二次执行（4）：
cur.next == null 推出循环
以上，实现单链表的倒转。
加载全部内容