LeetCode - Algorithms - 206. Reverse Linked List

Problem

206. Reverse Linked List

Follow up

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

Java

iteratively

1

© LeetCode – Reverse Linked List (Java) - Java Solution 1 - Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
		if (head == null || head.next == null)
			return head;

		ListNode p1 = head;
		ListNode p2 = p1.next;

		head.next = null;
		while (p1 != null && p2 != null) {
			ListNode t = p2.next;
			p2.next = p1;
			p1 = p2;
			p2 = t;
		}

		return p1;
    }
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
  • Memory Usage: 39 MB, less than 22.36% of Java online submissions for Reverse Linked List.

2

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; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
    	ListNode prev = null;
    	ListNode current = head;
    	ListNode next = null;
    	while(current!=null) {
    		next = current.next;
    		current.next = prev;
    		prev = current;
    		current = next;
    	}
    	head = prev;
        return head;
    }
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 0 ms
  • Your runtime beats 100.00 % of java submissions.

recursively

1

© LeetCode – Reverse Linked List (Java) - Java Solution 2 - Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
		if (head == null || head.next == null)
			return head;

		//get second node
		ListNode second = head.next;
		//set first's next to be null
		head.next = null;

		ListNode rest = reverseList(second);
		second.next = head;

		return rest;
    }
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
  • Memory Usage: 39.2 MB, less than 22.97% of Java online submissions for Reverse Linked List.

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
    	if (head==null || head.next==null)
    		return head;
    	ListNode p = reverseList(head.next);
    	head.next.next=head;
    	head.next=null;
        return p;
    }
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 1 ms
  • Your runtime beats 6.80 % of java submissions.

Tail Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseUtil(ListNode curr, ListNode prev) {
    	ListNode head = null;
    	if (curr.next==null) {
    		head = curr;
    		curr.next=prev;
    		return head;
    	}

    	ListNode next1 = curr.next;
    	curr.next=prev;
    	head = reverseUtil(next1,curr);
    	return head;
    }

    public ListNode reverseList(ListNode head) {
        if (head!=null)
          return reverseUtil(head,null);
        else
            return null;
    }
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 0 ms
  • Your runtime beats 100.00 % of java submissions.