Java in place O(n) solution: consider the linkedList as three parts


  • 0
    C

    The basic thought about this solution is to split the linkedlist into three sub linkedlists while knowing that each part could be empty.
    Key points:

    1. The number of item in the range (n,m) is n+m+1.

    2. A dummy head was created to facilitate the tracking of the current head since the initial head might get reversed.

    3. The purpose of the first While loop was to nail down the first part.

    4. The second while loop was the code actually do the reverse. Two references/pointers were used to track the head and tail of the second part.

    5. The rest of the linked list is the third part.

      public class Solution {
      public ListNode reverseBetween(ListNode head, int m, int n) {
      if(m==n || head == null || head.next == null) return head;
      int k = n-m+1;
      ListNode dummyHead,lastTail, reverseHead, reverseTail, temphead;
      //initialization
      reverseTail = null; reverseHead = null; temphead= null;
      dummyHead = new ListNode(0);
      dummyHead.next = head;
      lastTail = dummyHead;
      while(m!=1){
      lastTail = head;
      head = head.next;
      m--;
      }
      //start reversing
      while(k!=0){
      k--;
      temphead = head;
      head = head.next;
      if(reverseTail==null) {
      reverseHead = temphead;
      reverseTail = temphead;
      }else{
      temphead.next = reverseTail;
      reverseTail = temphead;
      }
      }
      //link three parts together
      if(reverseTail!=null)
      lastTail.next = reverseTail;
      if(reverseHead!=null)
      reverseHead.next = head;
      return dummyHead.next;
      }
      }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.