Reverse a singly linked list.
Hint:A linked list can be reversed either iteratively or recursively. Could you implement both?
Analysis:
For iteration, we need to have a prev and next node for temporal save.
For recursive,
Assume that the rest of the list had already been reversed, now how do I reverse the front part? Let’s assume the list is: n1 → … → nk-1 → nk → nk+1 → … → nm → Ø
Assume from node nk+1 to nm had been reversed and you are at node nk.
n1 → … → nk-1 → nk → nk+1 ← … ← nm
We want nk+1’s next node to point to nk.
So, nk.next.next = nk
Time complexity: O(n)
Space complexity: O(1)
Code is below:
/**
* 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) {
// O(n)
if (head == null || head.next == null) {
return null;
}
// iteration
ListNode current = head;
ListNode prev = null;
ListNode next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
// recursive
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
}
Followup:
Reverse a linked list from position m to n. Do it in-place and in one-pass.For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
Analysis:
Go through the list and find the position before m. Then start from m, reverse the n-m nodes like reverse linked list.
Time complexity: O(n)
Space complexity: O(1)
Code is below:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// O(n)
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
ListNode prev = dummy;
dummy.next = head;
// Find the position before the reverse start
for (int i = 0; i < m - 1; i++) {
prev = prev.next;
}
// Reverse the n - m nodes
ListNode cur = prev.next;
for (int i = 0; i < n - m; i++) {
ListNode next = cur.next;
cur.next = next.next;
next.next = prev.next;
prev.next = next;
}
return dummy.next;
}
}
CodeBySteven 