Reverse Linked List

发表于

非递归（迭代）

Analysis

由于链表不具有数组可以根据下标随机访问的特性，所以只能从头节点开始逐个的交换到最后一个节点，并且在每次交换过程中需要用两个变量：previous来保存原本处于current节点的前一个节点，previous在交换过程中变为current.next。除此之外，循环的条件是在current不为空的时候，当其为空时，它的previous是新的head。需记住将原头结点的后继设为空。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode previous=null;
        ListNode current=head;
        while(current!=null){
            ListNode temp=current.next;
            current.next=previous;
            previous=current;
            current=temp;
        }
        head=previous;
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: The new head of reversed linked list.
     */
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}

递归

Analysis

它利用递归走到链表的末端，然后再更新每一个node的next 值 (代码倒数第二句)。 在上面的代码中， reverseRest 的值没有改变，为该链表的最后一个node，所以，反转后，我们可以得到新链表的head。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution{
public:
    ListNode* reverseList(ListNode* head){
        //此处的条件不能写成if(head == NULL)
        if (head == NULL || head->next == NULL) return head;
        ListNode *newhead = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
    
        return newhead;
    }