Sequence list and linked list ----- advanced

common OJ topic ：

1. Now there is a head pointer of the linked list ListHead, The user enters a fixed value , Write a piece of code that will all be less than X The nodes of are in front of the other nodes , Moreover, the original data order cannot be changed , Returns the header pointer of the linked list after rearrangement ; The last linked list , The left is smaller than X The right side is larger than X( The original X Not necessarily in the linked list )

Ideas :

1) Now let's write a loop , Define a current To traverse the original single linked list , The cycle condition is current!=null

2) In the cycle , We have two things to do ( We will create two single linked lists A and B,A Is the storage ratio X Small nodes ,B Is the storage ratio X Big nodes )

3) In every linked list , Both the head node and the tail node must be defined ,HeadA and TailA,HeadB and TailB; Let's keep the head node still , Every time you insert an element , Only the tail nodes of the linked list are moved ;

Compare X Small data are put into HeadA Inside , Than X Big data is put into HeadB Inside

4) After the loop , There will be three situations

In the original linked list , Existing ratio X Small data , There's more than X Big data , therefore HeadA And HeadB There are data in it , This is what we can make TailA.next=HeadB;

In the original linked list , Only than X Big data , At this time HeadA The linked list pointed to is empty

In the original linked list , Only than X Small data , At this time HeadB The linked list pointed to is empty

5) After the linked list , There's an extreme situation ,HeadB There's only one element in it (HeadB=current), here TailA.next=HeadB; This is a new linked list and the synthesis is successful , But at this point, the last node Next Value is not empty , So we have to set it to empty manually ;

  public ListNode partition(ListNode head, int x) {
         ListNode HeadA=null;
      ListNode HeadB=null;
      ListNode TailA=null;
      ListNode TailB=null;
      ListNode current=head;
      while(current!=null)
      {
          if(current.val<x){
              if(HeadA==null)
              {
                  HeadA=current;
                  TailA=current;     
              }else{
                  TailA.next=current;
                  TailA=TailA.next;     
              }
          }else 
          {
              if(HeadB==null)
              {
                  HeadB=current;
                  TailB=current;     
              }else{
                  TailB.next=current;
                TailB=TailB.next;
              }
          }
          current=current.next;
      }
      if(HeadB==null)
      {  
          return HeadA;
      }else if(HeadA==null){
          TailB.next=null;
          return HeadB;
      }else{
          TailA.next=HeadB;
          TailB.next=null;
          return HeadA;
      } 

2. Delete all duplicate nodes in the sorted linked list  

1) The repeated nodes must be connected together , It's close together

2) There is more than one repeating element

Ideas : Create us or create a virtual node , Put all non duplicate nodes behind the virtual nodes ;

The main judgment condition is to define a node ,current Start by pointing to the header node , The outer loop traverses the original linked list , Just find out current.val!=current.next.val Then put current Put it in the newly created linked list

 public ListNode deleteDuplicates(ListNode head) {
        if(head==null)
        {
            return null;
        }
           ListNode HeadA=new ListNode(-1);
           ListNode TailA=HeadA;
           ListNode current=head;
           while(current!=null)
           {
               if(current.next!=null&&current.val==current.next.val)// The conditions cannot be written as if(current.val!=current.next.val) If the linked list has only one node , Then a null pointer exception will occur
               {
// If the data in this is 34,34,34,34,34,34, If the condition is current.val==current.nextval A null pointer exception will occur , because current Will go straight back , Until the last node is found current.next A null pointer exception will occur
                    while(current.next!=null&&current.val==current.next.val)
                    {
                        current=current.next;
                    }
// The resulting node is the last node of the repeating node
                    current=current.next;
               }else {
                  TailA.next=current;
                  TailA=TailA.next;
                  current=current.next;
               }
           }
           TailA.next=null;// Because the nodes assign values to each other , So if you say 12,12,34,45,45, The newly created linked list is found after the whole cycle next The value is not empty. , At this point, errors will occur in the linked list
Be sure to note that the last node of the newly created linked list must be empty
           return HeadA.next;
    }

3. Determine the palindrome structure of the linked list , Spatial complexity (O(1));

Input :1,2,2,1 Output ：true

Input :1,2 Output :true 

Their thinking : We still hope that it can traverse from back to front , So we need to reverse the single linked list after the intermediate node ;

1) Use the speed pointer , First find the middle node of the linked list

2) Flip , It is the two nodes that actually flip , The third node is used to calculate the value of the later node of the first two nodes next, Besides, it should be put in the first line of the loop

3) When we make retrospective judgments , Must from slow Go straight ahead ( There are only four nodes , take fast to glance at , After determining the intermediate node , And flip , At this time fast The value of has pointed to null , So we can't use fast Go back ;

4) After flipping , We're going to let slow Go from the back ,head Go from front to back , Know that two references meet ( Odd numbers )

5) If you find that slow.next=head perhaps slow=head In the middle, it means we have met , We all have to compare in the cycle head.data Is it equal to slow.data, If it's not equal , Go straight back to false;

 public boolean isPalindrome(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        ListNode current=null;
        ListNode currentNext=null;
        if(head==null)
        {
            return true;
        }
        //1 Find the middle node 
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
        }
        //2 Reverse the single linked list 
        current=slow.next;
        while(current!=null)
        {
            currentNext=current.next;
            current.next=slow;
            slow=current;
            current=currentNext;
        }
        //3 Make a judgment on whether it will be written , First, treat it as an odd number ( Let's put even numbers aside ), Write the complete code , When all is done , Then write the complete code from the loop 
        while(head!=slow)
        {
            if(head.val!=slow.val)
            {
                return false;
            }
            if(head.next==slow)
            {
                return true;
            }
          
            slow=slow.next;
            head=head.next;
        }
        return true;

    }

4. The list intersects , Return to the intermediate node

1) First of all, we have to figure out a problem , If two linked lists intersect , So what's the shape Y Shape or X The shape of the

2) If two linked lists intersect , So val The domain is the same or next The domain is the same ?

yes Y The shape of the , And intersect linked lists next The domain is the same ;

 

How to do it :

1) If the length of two single linked lists is different , Then they go from the beginning , Then they will never meet

2) We first need to know the length of the two linked lists , Let the long linked list take the difference step first ( The difference between the length of two linked lists )

3) We are making them walk step by step at the same time

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null)
        {
            return null;
        }
        int count1=0;
        int count2=0;
        int len=0;
        ListNode current1=headA;
        ListNode current2=headB;
        while(current1!=null)
        {
            current1=current1.next;
            count1++;
        }
        while(current2!=null)
        {
            current2=current2.next;
            count2++;
        }
        current1=headA;
        current2=headB;
        if(count1>count2)
        {
            len=count1-count2;
            while(len!=0)
            {
              current1=current1.next;
              len--;
            }
        }else{
            len=count2-count1;
            while(len!=0)
            {
                current2=current2.next;
                len--;
            }
        }
        while(current1!=current2)// Why not judge current1.next!=current2.next As a condition of judgment , Finally we go back current1.next
        {
            current1=current1.next;
            current2=current2.next;
        }
        return current1;

    }

5. Determine if the list has links  

We define a speed pointer , Define a fast pointer fast, Two steps at a time , Let's define a slow pointer , One step at a time ;

Why not take three steps at a time , One step at a time ？

We have to wait until after each walk before we can compare , It may be slower than walking two steps at a time , It is also possible to never meet ; 

When we give examples , Take a ring with only two nodes , And then go through two steps and three steps , drawing

 public boolean hasCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast)
            {
                return true;
            }
        }
        return false;
    }

6. Returns the first node when the linked list enters the ring (OJ), If the linked list has no ring, it returns null , The space complexity is O(1)

 

 

Answer key : In the figure above , We can find the encounter node that defines the fast pointer and the slow pointer , We definitely need to find the node that meets ;

set up : The distance from the starting point to the entry point is X, We assume that the distance between the meeting point and the entry point is Y, The length of the ring is C

Then at this time fast The journey is slow It's a long way to go 2 times

Let's count the time when we met slow The journey and fast The journey ( Go clockwise )

because fast The speed of slow Of 2 times , They had met at the same time , therefore fast My journey is slow Of 2 times ;

slow The journey :X+C-Y

fast The journey :X+C+C-Y

Suppose you've only walked one circle ,fast I only walked one circle , We met on the second lap ; Continuous standing , Find out X=Y;

Then we come to the conclusion that : The distance from the starting point to the entry point , And the distance from the entry point to the meeting point is the same ;

We define two nodes, one from the head of the linked list , One goes back from the middle position , The meeting node is the entry node of the ring ;

But in fact, it may fast Will walk many circles ,slow The journey is the same

2(X+C-Y)=X+NC+C-Y

X=(N-1)C+Y

N Is arbitrary ,X It must be certain , Because the distance between the starting point and the entry point is certain , Now? N and C It's uncertain , The more you turn , explain C The smaller , It means that the distance of one circle is very small ;

slow It's impossible to make many turns in the ring

  public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
// If you don't write this if sentence , The code will be recycled ,fast==slow, Just in time , No conditions ,fast and slow Will go straight down 
// So we agreed , As long as we meet , Then quit 
            if(fast==slow)
            {
                break;
            }
        }
// At this point, the code can go here in two cases , One is fast=null perhaps fast.next=null, This belongs to fast The pointer has reached the end of the linked list , here slow It's the middle node 
        if(fast==null||fast.next==null)
        {
            return null;
        }
        while(slow!=head)
        {
            head=head.next;
            slow=slow.next;
        }
        return slow;
        
    }