Skip to content

Instantly share code, notes, and snippets.

@InterviewBytes InterviewBytes/ListNode.java Secret
Created Jun 9, 2017

Embed
What would you like to do?
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.
package com.interviewbytes.linkedlists;
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
package com.interviewbytes.linkedlists;
public class ReverseBetween {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode sentinel = new ListNode(0);
sentinel.next = head;
ListNode prev = sentinel;
int index = 0;
while (index < m - 1) {
prev = prev.next;
index++;
}
ListNode current = prev.next;
ListNode start = prev.next;
ListNode reverse = null;
while (index < n) {
ListNode next = current.next;
current.next = reverse;
reverse = current;
current = next;
index++;
}
prev.next = reverse;
start.next = current;
return sentinel.next;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.