定義一個(gè)函數(shù)，輸入一個(gè)鏈表的頭節(jié)點(diǎn)，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)。

示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

1.雙指針

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode pre = null, lat = head;
        // ListNode dummy = lat;
        while(lat != null){
            ListNode tmp = lat.next;
            // ListNode tmp1 = lat;
            // lat.next = pre;
            // pre = tmp1;
            // lat = tmp;
            lat.next = pre;
            pre = lat;
            lat = tmp;
        }
        return pre;
    }
}

2.遞歸

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode node = reverseList(head.next);
        // if(node == null){
        //     return head;
        // }else{
            // node.next = head;//???node一直是5開頭，node每次更換下一個(gè)，所以最后5，1
            head.next.next = head;
            head.next = null;
        // }
        return node;
    }
}

3.棧

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        Stack<Integer> stack = new Stack<Integer>();
        while(head!=null){
            stack.push(head.val);
            head = head.next;
        }
        if(stack.isEmpty()){
            return null;
        }
        ListNode node = new ListNode(stack.pop());
        ListNode pre = node;//記錄一下頭
        while(!stack.isEmpty()){
            ListNode dummy = new ListNode(stack.pop());
            node.next = dummy;
            node = node.next;
        }
        return pre;


    }
}