反转链表
反转链表
http://www.nowcoder.com/questionTerminal/75e878df47f24fdc9dc3e400ec6058ca
第一种：递归法
解释一下：
经过head.next.next=head;使得head.next的next指针指向head
经过head.next=null;使得head的next指针指向空
所以这两句语句的作用就是使head与head->next的指向反转。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
//递归实现
if(head==null||head.next==null){//链表为空或者只有一个元素
return head;
}
//先反转后面的链表，走到链表的末端结点
ListNode p = ReverseList(head.next);
//再将当前节点设置为后面节点的后续节点
head.next.next=head;
head.next=null;
return p;
}
} 第二种：头插法
解释：这里涉及到head，pre，next三个结点
作用：使原本指向为head->(head->next)变为(head->next)->head
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null||head.next==null){//该链表无结点或只有一个结点
return head;
}
ListNode pre = null;
ListNode next = null;
while(head!=null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
} 第三种：遍历+栈保存
最后，附上测试代码，只需改动ReverseList函数的内容，其他无需改动
class ListNode {
int val;
ListNode next = null;
public ListNode(int val) {
this.val = val;
}
}
class Solution {
public static ListNode ReverseList(ListNode head) {
//递归实现
if(head==null||head.next==null){//链表为空或者只有一个元素
return head;
}
//先反转后面的链表，走到链表的末端结点
ListNode p = ReverseList(head.next);
//再将当前节点设置为后面节点的后续节点
head.next.next=head;
head.next=null;
return p;
}
public static void Myprint(ListNode t1)
{
while(t1!=null){
System.out.println(t1.val);
t1=t1.next;
}
}
public static void main(String[] args) {
ListNode t1 = new ListNode(1);
ListNode t2 = new ListNode(2);
ListNode t3 = new ListNode(3);
t1.next=t2;
t2.next=t3;
t3.next=null;
Myprint(t1);
System.out.println("--------反转之后的链表-------");
ListNode r = ReverseList(t1);
Myprint(r);
}
} 
华为工作强度 817人发布