[classic example] classic list questions @ list

I believe you will encounter the same situation as me when you first learn data structure. Problems cannot constitute effective ideas .

Through continuous practice, I believe we will also become big guys , It will also be taken to the big factory offer.

---

List sorting

First of all, we know the idea of solving this problem according to the topic It will probably use ①  Double pointer ② List sorting  

1. Set up fast and slow Two pointers use fast Take two steps slow The principle of taking one step will slow Set as the intermediate node of the linked list , And then pre Pointer to slow Pointer to the previous node . So now we will pre Pointer to a null, You can divide the original linked list into two parts .

2. Sort the two-part linked list . In order to complete the next action .

3. To this step The two parts of the linked list are in good order , Create a new node header Compare The value of the two chain header nodes , Use the new linked list node to connect with the party with small value .

4. Complete all steps Just return to the set node .

class Solution {
    public ListNode sortList(ListNode head) {
       return mergeSort(head); }
    ListNode mergeSort(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        while(fast != null && fast.next != null){// Use the speed pointer to find the middle node of the linked list 
            pre = slow;// here pre  stay last In the previous position 
            fast = fast.next.next;
                slow = slow.next;
          }
           pre.next = null;// bring pre Of next It's empty   In this way, the linked list is divided into two parts   Part in head start   Part in slow start 
         ListNode l1 =  mergeSort(head); Use merge sort to sort the two parts of the linked list 
         ListNode l2 =  mergeSort(slow);
         return  merge(l1, l2);
        }
      ListNode merge(ListNode l1, ListNode l2){
        ListNode newhead = new ListNode(0); Create a new chain header 
        ListNode cur3 = newhead;
      while(l1 != null && l2 != null){
         if(l1.val < l2.val){ Compare the value of the two linked lists 
             cur3.next = l1; use cur3  Connect 
             l1 = l1.next;
             }else{
             cur3.next = l2;
             l2 = l2.next;
            }
            cur3 = cur3.next;
          }
          if(l1 != null){
              cur3.next = l1;
          }
          if(l2 != null){
              cur3.next = l2;
          }
          return newhead.next;
    }
}

---

Delete duplicate elements from the sort list  

  

Their thinking

As usual, we should judge the special situation first

Create a new node connector node The use of l2 To adjudicate   see l2.val Values and l2.next.val Are they the same? .

This step introduces you

As we enter if In the loop On behalf of l2.val == l2.next.val When we while Walk the     It means that the current value is different from the next value

At this time, we are still if Inside In order to prevent it from being followed by the same set of values We need to continue this sentence of continuous judgment in the cycle .

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) return head;
      ListNode newhere = new ListNode (0); Create a new node 
      newhere.next = head;
      ListNode l1 = newhere;
      ListNode l2 = head;
   while(l2 != null){ The loop condition  l2 Can't be empty 
      if(l2.next != null && l2.val == l2.next.val){ Now judge l2  Of val  and l2.next Of val Are they the same? 
            while(l2.next != null && l2.val == l2.next.val){ This step is crucial   Will explain clearly in the problem-solving ideas 
                l2 = l2.next;
            }
            l1.next = l2.next;
            l2 = l1.next;
          }else{
              l1 = l2;
              l2 = l2.next;
          }
      }
      
       return newhere.next;
     
    }
}

  Rearrange the list

 

  

Understand the meaning of the question Is to connect the first and last The second one is connected with the penultimate one In turn Until the position of the middle most element

Use the speed pointer to operate Find the middle element It is divided into two linked list parts Reverse the second half Make the last element become the first element, and then merge .

class Solution {
    public void reorderList(ListNode head) {
    ListNode fast = head.next;
    ListNode slow = head;
    while(fast != null && fast.next != null){ The speed pointer operates 
        fast = fast.next.next;
        slow = slow.next;
    }
    ListNode pre = slow.next;
    ListNode cur1 = null;
    slow.next = null;
    while(pre != null){ Reverse linked list operation 
    ListNode cur =  pre.next;
    pre.next = cur1;
    cur1 = pre;
    pre = cur;
 }
 ListNode cur3 = head;
  ListNode l3 = cur1;
   while(cur3 != null && l3 != null){
       ListNode l1 = cur3.next; Merge two linked lists 
       ListNode l2 = l3.next;
        cur3.next = l3;
        cur3 = l1;
          l3.next = cur3;
        l3 = l2;


   }
    }
}

  Delete continuous nodes with a total value of zero from the linked list

 

Their thinking

Continue to traverse nodes and add them together Operate when it is judged to be zero .

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
       ListNode pre = new ListNode(0);
       ListNode cur =pre;
       pre.next = head;
      while(pre != null){
           ListNode cur1 = pre.next;
           int sum = 0;
           while(cur1 != null){ When the sum of calculation is zero 
               sum += cur1.val;
               cur1 = cur1.next;
               if(sum == 0){ When you find what you need 
                   pre.next = cur1; To delete 
                   break;
               }
           }
           if(cur1 == null) pre = pre.next;
      
      }
       return cur.next;
    }
}

---

  Reverse a linked list

When we see this question, we will think that we should find it first right The next node and left The previous node . This is convenient for us to reverse . And so it is  

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
     ListNode node = new ListNode(0);
     node.next = head;
     ListNode pre = node;
     for(int i = 1; i < left; i ++){ First find left The previous node 
         pre = pre.next;

     }
     ListNode haed = pre.next; take haed Insert the first element to reverse 
     for(int j = left; j < right; j ++  ){ The following part is reversed 
         ListNode nex = haed.next;
         haed.next = nex.next;
         nex.next = pre.next;
         pre.next = nex;
     }
     return node.next;
    } Finally, output the header node 
}

I believe tomorrow will be better ！！！🤭