剑指Offer之反转链表

题目描述
输入一个链表，反转链表后，输出链表的所有元素。

思路一：从输入链表中循环取出节点作为新链表的头节点。

public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

public ListNode reverseList(ListNode head) {
    if(head==null){
        return null;
    }
    ListNode newHead=head;
    ListNode tempNode=head.next;
    newHead.next=null;
    while(tempNode!=null){
        final ListNode node=tempNode;//取当前节点
        tempNode=tempNode.next;//循环取下一个节点
        node.next=newHead;//当前节点next指向新链表头节点
        newHead=node;
    }
   return newHead;    
}

思路二：从输入链表第三个开始插入到头节点后面，最后把头节点的next指向null，第二个节点next指向原头节点，完成反转，如下图示意：

反转链表1.png

    public class ListNode {
        int val;
        ListNode next = null;
        ListNode(int val) {
            this.val = val;
        }
     }
     public ListNode reverseList(ListNode head) {
         if(head==null||head.next==null){
            return head;
         }
         ListNode listSecond=head.next;//记录第二个节点，最后一步它要指向第一个节点。
         ListNode tempNode=listSecond.next;//从第三个节点开始插入头节点后面
         ListNode result=null;
         while(tempNode!=null){
             final ListNode node=tempNode;//获取当前节点
             tempNode=node.next;//tempNode变下一个节点
             if(node.next==null){
                 result=node;
             }
             final ListNode headNext=head.next;//获取头结点的next。
             head.next=node;//插入头结点后
             node.next=headNext;
         }
         listSecond.next=head;
         head.next=null;
         if(result==null){//如果只有两个节点，result为null
             result=listSecond;
         }
         return result;
    }

反转链表还有其他思路，这里就提供两种思路供参考。