Java O(n) O(1) reference knfdksnf


#1
/**
  • Definition for singly-linked list.

  • class ListNode {

  • public int val;
    
  • public ListNode next;
    
  • ListNode(int x) { val = x; next = null; }
    
  • }
    */
    public class Solution {
    public ListNode solve(ListNode A) {

    if(A.next==null)
    return A;

    if(A.next.next==null)
    return A;
    ListNode evenHead=null;
    ListNode oddHead=null;

    ListNode lastEven=null;
    ListNode lastOdd=null; //// 1–2--3–4

    ListNode givenHead=A;

    int count=1;
    while(givenHead!=null)
    {
    if(count%2!=0)
    {
    if(oddHead==null)
    {
    oddHead=givenHead;
    lastOdd=givenHead;
    }else{
    lastOdd.next=givenHead;
    lastOdd=lastOdd.next;

          }
          
       }else{
          
          if(evenHead==null)
          {
              evenHead=givenHead;
              lastEven=givenHead;
          }else{
             lastEven.next=givenHead;
             lastEven=lastEven.next; 
              
          }
           
       }
       
       givenHead=givenHead.next;
       count++;
    

    }

    lastOdd.next=null;
    lastEven.next=null;

    //////reversing pointer of even List

    ListNode cur=evenHead;
    ListNode prev=null;
    ListNode next=null;

    // return oddHead;
    while(cur!=null)
    {
    next=cur.next;
    cur.next=prev;
    prev=cur;
    cur=next;
    }

    evenHead=prev;

    ///return evenHead;
    ListNode reqNode=null;
    ListNode resHead=null;
    ListNode oddNode=oddHead;
    ListNode evenNode=evenHead;

    int count1=1;
    while(oddNode!=null && evenNode!=null)
    {
    if(count1%2!=0)
    {
    if(resHead==null)
    {
    resHead=oddNode;
    reqNode=oddNode;
    //oddNode=oddNode.next;
    }else{
    resHead.next=oddNode;
    resHead=resHead.next;
    //oddNode=oddNode.next;
    }

          oddNode=oddNode.next;
      }else{
          
           resHead.next=evenNode;
           resHead=resHead.next;
           evenNode=evenNode.next;
          
      }
      
     count1++; 
    

    }

    while(oddNode!=null)
    {
    resHead.next=oddNode;
    resHead=resHead.next;
    oddNode=oddNode.next;
    }

    while(evenNode!=null)
    {
    resHead.next=evenNode;
    resHead=resHead.next;
    evenNode=evenNode.next;
    }

    // resHead.next=null;

    return reqNode;

    }
    }