Leetcode-02 (linked list question)

  Iterative method ：

Ideas ： Divide a local location , Then use an auxiliary node and auxiliary pointer , Compare the size and then connect the auxiliary pointer , Push back every time ;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  // Auxiliary iteration method 
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
      ListNode help=new ListNode(-1);
      ListNode pre=help;// Auxiliary pointer 

      // Traverse 
       while (l1 != null && l2 != null){
        if(l1.val<=l2.val){
          // Connect 
          pre.next=l1;
          pre=pre.next;
          l1=l1.next;
        }else{
            pre.next=l2;
            pre=pre.next;
            l2=l2.next;
        }
      }
      // Connect the remaining nodes directly 
      if(l1!=null){
        pre.next=l1;
      }
      if(l2!=null){
        pre.next=l2;
      }
           
      return help.next;
    }
}

The recursive method

class Solution {
  // recursive 
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //1. The end condition 
    if(l1==null){
      return l2;
    }
    if(l2==null){
      return l1;
    }
    //2. Recursive thinking 
    if(l1.val<=l2.val){
      l1.next=mergeTwoLists(l1.next,l2);
      return l1;
    }else{
        l2.next=mergeTwoLists(l1,l2.next);
        return l2;
    } 

    
    }
}

 

The recursive method , Similar to the above

class Solution {
    // recursive 
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //1. The end condition 
        if(list1==null){
         return list2;
        }
        if(list2==null){
         return list1;
        }

        //2. Recursive thinking 
        if(list1.val<=list2.val){
          list1.next=mergeTwoLists(list1.next,list2);
          return list1;
        }else{
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}

 

Iterative method

Pay attention to the use of pointer pointing head, Then point to the previous node , Push back slowly

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
          ListNode pre=null;
          ListNode cur=head;
          // Each cycle is exchanged in pairs 
          while(cur!=null){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
          }
          return pre;
    }

Speed pointer ：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            ++n;
            cur = cur.next;
        }
        int k = 0;
        cur = head;
        while (k < n / 2) {
            ++k;
            cur = cur.next;
        }
        return cur;
    }
}