Python Iterative AC Code, reverse the second half first


  • 0
    B
    class Solution:
    # @param head, a ListNode
    # @return nothing
    def reorderList(self, head):
        if not head or not head.next:
            return head
        
        length=0
        node=head
        while node:
            node=node.next
            length+=1
        
        if length==2:
            return head
            
        pre=head
        count=1
        while count<(length-1)//2:
            pre=pre.next
            count+=1
        
        pre=pre.next
        cur=pre.next
        while cur:
            
            nxt=cur.next
            cur.next=pre
            pre=cur
            cur=nxt
            
        start=head    
        last=pre
        count=length//2
        
        while count>0:
            temps=start.next
            templ=last.next
            start.next=last
            if count==1 and length%2==0:
                last.next=None
                break
            elif count==1 and length%2==1:
                last.next=temps
                temps.next=None
                break
            else:
                last.next=temps
            
            start=temps
            last=templ
            count-=1
    

    For example, for linked list 1->2->3->4-5, the code first makes the list to be 1->2->3<-4<-5
    then from 1 and 5, it is easy to concatenate respectively. Make sure remember to make 3->None in the end.

    For even number linked list: 1->2->3->4, make first 1->2<-3<-4, count carefully how many concatenation is necessary and make sure lastly, make 3->None


  • 0
    C

    Hi, you made a small mistake, for linked list 1->2->3->4-5, the code first makes the list to be 1->2->3->4<-5 and 4->None, not as 1->2->3<-4<-5. For even number linked list: 1->2->3->4, make first 1->2->3<-4 and 3->None, not as 1->2<-3<-4, and lastly make 2->None.


Log in to reply
 

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