[LeetCode] 206. Reverse Linked List

Reverse a singly linked list.

click to show more hints.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Thought process:

1. Iterative: iterate through the linked list. Use a previous pointer that points to the node before the current node. Change current.next to previous.
2. Recursive: use a helper function that passes in the previous node along with head.
1. Base case: head == null, return previous.
2. Otherwise: reverse list and proceed to next node.

Solution 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

/** * 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; while (head != null) { ListNode next = head.next; head.next = previous; previous = head; head = next; } return previous; } }

Time complexity: O(n).

Solution 2:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

/** * 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) { return reverseList(null, head); } private ListNode reverseList(ListNode previous, ListNode head) { if (head == null) { return previous; } ListNode next = head.next; head.next = previous; return reverseList(head, next); } }

Time complexity: O(n).