剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

方法一：利用栈的思想，将所有value值压入栈后再取出，并创建一条新的链表来接收他。

在此过程中，学习到了“JAVA中并无指针”的概念，Java中的所有变量名都是对对象的引用。可以参考：(26条消息) Java与指针_空谷回响的编码史-CSDN博客_java指针

import java.util.linkedList;
public class 剑指24_反转链表 {
    public class ListNode{
        int val;
        ListNode next;
        ListNode(int x)  { val = x; }
    }
    public ListNode reverseList(ListNode head){
        //用a-b-c-d链表做示例
        //方法一 栈     放弃原链表，创建一条新的链表，值是原链表的反转
        linkedList a = new linkedList();
        int count = 0;
        if(head == null || head.next == null)   //NullPointerException || NoSuchElementException
            return head;
        while(head != null){
            a.addLast(head.val);
            head = head.next;
            count ++;
        }
        ListNode newhead = new ListNode((int)a.removeLast());
        ListNode temp = newhead;
        for(int i = 1;i < count; i++){
            ListNode p1 = new ListNode((int)a.removeLast());
            temp.next = p1;
            temp = p1;
        }
        return newhead;
    }
}

方法二：双指针赋值。但Java中没有指针，所以其实就是两个引用之间来回赋值。搞不清楚可以画个图帮助理解。

import java.util.linkedList;

public class 剑指24_反转链表 {
    public class ListNode{
        int val;
        ListNode next;
        ListNode(int x)  { val = x; }
    }
    public ListNode reverseList(ListNode head){
//方法二 双指针   建议搭配画图法使用
        ListNode cur = head;
        ListNode pre = null;
        ListNode temp;
        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

方法三：递归反转，也可以作为剑指06的参考

import java.util.linkedList;

public class 剑指24_反转链表 {
    public class ListNode{
        int val;
        ListNode next;
        ListNode(int x)  { val = x; }
    }
    public ListNode reverseList(ListNode head){
        if(head == null || head.next == null)
            return head;
        ListNode tail = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return tail;
    }
}