206. Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Java

// Non-Recursive
class Solution {
    ListNode newHead = null;
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        reverse(head);
        return newHead;
    }
    private ListNode reverse(ListNode head) {
        if (head.next == null){
            newHead = head;
            return newHead;
        } 

        // swap
        ListNode temp = reverse(head.next);
        temp.next = head;
        head.next = null;
        return head;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, prev = null, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = prev;

            // shift to next node
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

// Recursive
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverseRec(head, null);
    }
    private ListNode reverseRec(ListNode head, ListNode newHead) {
        if (head == null) return newHead;
        ListNode next = head.next;
        head.next = newHead;
        return reverseRec(next, head);
    }
}

Python

反轉串列，把上個，這個，下個順序反轉
遞迴版本就把下個變這個，直到結束
Python語法很方便

# T:O(n), S:O:(1)
# Definition for singly-linked list.
# class ListNode:
#     def init(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head # end, start
        while curr != None:
            curr.next, prev, curr  = prev, curr, curr.next # reverse curr and prev, curr go next
        return prev
        
# recursive version
class Solution:
    def reverseList(self, head):
        if head is None or head.next is None:
            return head
        result = self.reverseList(head.next) # go through
        head.next.next,head.next = head,None # reverse
        return result

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)