Programming

Leetcode-206. Reverse Linked List

By PattySung 28 June 2023
Leetcode-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: []

<解題>

image

1. iterative solution


class Solution {
    public ListNode reverseList(ListNode head) {
    ListNode prev = null; //建新的linkedlist
    while (head != null) {
        ListNode next_node = head.next;
        head.next = prev;
        prev = head;
        head = next_node;
    }
    return prev;
}
}

2. recursive solution


class Solution {
    public ListNode reverseList(ListNode head) {
    return reverseListInt(head, null);
}

    private ListNode reverseListInt(ListNode head, ListNode newHead) {
        if (head == null)
            return newHead;
        ListNode next_node = head.next;
        head.next = newHead;
        return reverseListInt(next_node, head);
    }
}