柠檬微趣笔试题-反转单链表

看到反转链表，可能第一时间的想法便是遍历一遍这个单链表，然后把链表里的元素都取出来，放到一个数组里，然后逆置这个数组。这个想法是错的！！！

反转一个单链表，我们需要的是改变这个链表内节点的指向。

反转链表第一步：

判断链表是否为空，如果链表为空，则直接返回null。

if (this.head == null) { //没有节点
return null;
}

反转链表第二步：

判断链表是否只有一个节点，如果头结点的下一节点等于空，则说明该链表只有一个节点，即返回头结点。

反转链表第三步：

if (this.head.next == null) { //只有一个节点
return this.head;
}

//至少两个节点

第三步详解如下：

Node cur=this.head.next;
this.head.next=null;
while (cur!=null){
Node curNext=cur.next;
cur.next=head;
this.head=cur;
cur=curNext;
}
return head;

链表反转后，它原本的头结点的下一节点就为空null了。但是不能在一开始就将头结点的下一节点置为空。因为将它置为空后，便失去了与链表本来head.next的联系；所以，我们定义一个cur记录头结点下一节点的位置；也就是说让head不动，将记录头结点下一节点位置的cur用头插法的方式插入到head的前边，在cur头插到head前再定义一个curNext记录cur的下一节点，使cur到了head前，也不会失去与后边节点的联系。当所有的链表都反转后，cur就会为空。

完整代码如下：

class Node{
public int val;
public Node next; //类型是Node null

public Node(int val){
this.val=val;}

}

public class SingleLinkedList {
public Node head; //反转链表
//反转链表并不能使用逆置数组，需要改变链表元素的指向（使用头插法）
public Node reverseList() {
if (this.head == null) { //没有节点
return null;
}
if (this.head.next == null) { //只有一个节点
return this.head;
}
//至少有两个节点
Node cur=this.head.next;
this.head.next=null;
while (cur!=null){
Node curNext=cur.next;
cur.next=head;
this.head=cur;
cur=curNext;
}
return head;
}
}