LeetCode反轉(zhuǎn)鏈表的方式有哪些

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

示例:

限制：

鏈表的反轉(zhuǎn)是老生常談的一個問題了，同時也是面試中?？嫉囊坏李}。最簡單的一種方式就是使用棧，因為棧是先進后出的。實現(xiàn)原理就是把鏈表節(jié)點一個個入棧，當全部入棧完之后再一個個出棧，出棧的時候在把出棧的結(jié)點串成一個新的鏈表。原理如下

   

代碼比較簡單，來看下

 1public ListNode reverseList(ListNode head) {
2    Stack<ListNode> stack = new Stack<>();
3    //把鏈表節(jié)點全部摘掉放到棧中
4    while (head != null) {
5        stack.push(head);
6        head = head.next;
7    }
8    if (stack.isEmpty())
9        return null;
10    ListNode node = stack.pop();
11    ListNode dummy = node;
12    //棧中的結(jié)點全部出棧，然后重新連成一個新的鏈表
13    while (!stack.isEmpty()) {
14        ListNode tempNode = stack.pop();
15        node.next = tempNode;
16        node = node.next;
17    }
18    //最后一個結(jié)點就是反轉(zhuǎn)前的頭結(jié)點，一定要讓他的next
19    //等于空，否則會構(gòu)成環(huán)
20    node.next = null;
21    return dummy;
22}

雙鏈表求解是把原鏈表的結(jié)點一個個摘掉，每次摘掉的鏈表都讓他成為新的鏈表的頭結(jié)點，然后更新新鏈表。下面以鏈表1→2→3→4為例畫個圖來看下。

 1public ListNode reverseList(ListNode head) {
2    //新鏈表
3    ListNode newHead = null;
4    while (head != null) {
5        //先保存訪問的節(jié)點的下一個節(jié)點，保存起來
6        //留著下一步訪問的
7        ListNode temp = head.next;
8        //每次訪問的原鏈表節(jié)點都會成為新鏈表的頭結(jié)點，
9        //其實就是把新鏈表掛到訪問的原鏈表節(jié)點的
10        //后面就行了
11        head.next = newHead;
12        //更新新鏈表
13        newHead = head;
14        //重新賦值，繼續(xù)訪問
15        head = temp;
16    }
17    //返回新鏈表
18    return newHead;
19}

我們再來回顧一下遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。

 1public ListNode reverseList(參數(shù)0) {
2    if (終止條件)
3        return;
4
5    邏輯處理（可能有，也可能沒有，具體問題具體分析）
6
7    //遞歸調(diào)用
8    ListNode reverse = reverseList(參數(shù)1);
9
10    邏輯處理（可能有，也可能沒有，具體問題具體分析）
11}

if (head == null || head.next == null)    return head;

 1public ListNode reverseList(ListNode head) {
2    //終止條件
3    if (head == null || head.next == null)
4        return head;
5    //保存當前節(jié)點的下一個結(jié)點
6    ListNode next = head.next;
7    //從當前節(jié)點的下一個結(jié)點開始遞歸調(diào)用
8    ListNode reverse = reverseList(next);
9    //reverse是反轉(zhuǎn)之后的鏈表，因為函數(shù)reverseList
10    // 表示的是對鏈表的反轉(zhuǎn)，所以反轉(zhuǎn)完之后next肯定
11    // 是鏈表reverse的尾結(jié)點，然后我們再把當前節(jié)點
12    //head掛到next節(jié)點的后面就完成了鏈表的反轉(zhuǎn)。
13    next.next = head;
14    //這里head相當于變成了尾結(jié)點，尾結(jié)點都是為空的，
15    //否則會構(gòu)成環(huán)
16    head.next = null;
17    return reverse;
18}

1public ListNode reverseList(ListNode head) {
2    if (head == null || head.next == null)
3        return head;
4    ListNode reverse = reverseList(head.next);
5    head.next.next = head;
6    head.next = null;
7    return reverse;
8}

 1public ListNode reverseList(ListNode head) {
2    return reverseListInt(head, null);
3}
4
5private ListNode reverseListInt(ListNode head, ListNode newHead) {
6    if (head == null)
7        return newHead;
8    ListNode next = head.next;
9    head.next = newHead;
10    return reverseListInt(next, head);
11}

 1public ListNode reverseList(ListNode head) {
2    return reverseListInt(head, null);
3}
4
5private ListNode reverseListInt(ListNode head, ListNode newHead) {
6    if (head == null)
7        return newHead;
8    ListNode next = head.next;
9    head.next = newHead;
10    ListNode node = reverseListInt(next, head);
11    return node;
12}