Arrays and linked lists

Find rotation array

Ideas ：1. Find median 2. If a[l] < a[m] Explain the order on the left If x < a[l]  Explain that the target number is on the right , On the left  

import java.util.*;
 
public class Finder {
    public int findElement(int[] a, int n, int x) {
        // write code here
        int l = 0, r = n-1;
//  Be careful   Must have an equal sign 
        while (l <= r) {
            int m = l + (r-l)/2;
            if (a[m] == x) return m;
            if (a[m] > x) {
                // The front is orderly 
                if (a[l] < a[m] && x < a[l]) {
                    l = m+1;
                }else {                    
                    r = m-1;
                }
            }else {
                // The back is orderly 
                if (a[m] < a[r] && x > a[r]) {
                    r = m-1;;
                }else {
                    l = m+1;
                }
            }
        }
        return -1;
    }
}

Merge range

In array intervals Represents a set of intervals , The single interval is intervals[i] = [starti, endi] . Please merge all overlapping intervals , And return a non overlapping interval array , The array needs to cover exactly all the intervals in the input .

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length ==0 || intervals.length == 1) return intervals;
//     Sort according to the first element from small to large 
        Arrays.sort(intervals, (a1,a2) -> a1[0] - a2[0]);
        int[] tmp = intervals[0];
        List<int[]> res = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
//     If the second element of the first array is smaller than the first element of the second array , Explain that there is no need to merge 
            if (tmp[1] < intervals[i][0]) {
                res.add(tmp);
                tmp = intervals[i];
            } else {
//     Otherwise, find the maximum value of the second element of the two arrays as the combined second element 
                tmp[1] = Math.max(tmp[1], intervals[i][1]);
            }
        }
//     Save the last merged array 
        res.add(tmp);
        int[][] ans = new int[res.size()][];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }
}

Longest non repeating subarray

Given a length of n Array of arr, return arr The length of the longest non repeating element subarray of , No repetition means that all numbers are different .

Subarray is continuous , such as [1,3,5,7,9] The subarrays of are [1,3],[3,5,7] wait , however [1,3,7] It's not a subarray

  public static int lengthOfLongestSubstring(int[] ss) {
    if (ss == null) return 0;

    Map<Integer,Integer> map = new HashMap<>();

    int len = ss.length;
    int max = 0;

// Double pointer marks the start and end subscripts of the non repeating subarray 
    for (int s = 0, e = 0; e < len; e++) {

// If it is repeated, the starting point is modified to one digit after the repeated number 
      if (map.containsKey(ss[e])) {
        s = Math.max(map.get(e)+1,s);
      }
// Put in numbers and subscripts 
      map.put(ss[e],e);
// Compare the maximum length 
      max = Math.max(max,(e-s+1));
    }

    return max;
  }

Merge K A sort list

Ideas ：1. 2 An ordered list merges 2. Merge with merge , The time complexity is O(NlogN)

class Solution {
    public ListNode mergeKLists(ListNode[] nodes) {
        if (nodes == null || nodes.length == 0) return null;
        
        return merge(lists, 0, nodes.length-1);
    }
    private ListNode merge(ListNode[] lists, int lo, int hi) {
    	// base case
        if (lo == hi) {
            return lists[lo];
        }
        int mid = lo + (hi - lo) / 2;
        //  Recursively merge the two parts before and after 
        ListNode l1 = merge(lists, lo, mid);
        ListNode l2 = merge(lists, mid + 1, hi);
        return mergeTwoLists(l1, l2);
    }

    public ListNode mergeTwo (ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                cur.next = l2;
                return res.next;
            }
            if (l2 == null) {
                cur.next = l1;
                return res.next;
            }
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return res.next;
    }
}

K A set of flip list

Ideas ：1. Double pointer , Let's go first k Step , reverse s To e.

2. After reversal e It's the head pointer ,s The next one is the linked list after recursive inversion .

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        ListNode s = head, e = head;
        int i = k;
        while (i-- > 0) {
            if (e == null) return head;
            e = e.next;
        }

        ListNode newHead = reverse(s, e);
        s.next = reverseKGroup(e, k);
        return newHead;
    }
    public ListNode reverse(ListNode cur, ListNode e) {
        ListNode pre = null;
        ListNode next = null;
        while (cur != e) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

Reverse from position  m  To  n  The linked list of . Please use a scan to complete the inversion

Ideas ：1. Speed pointer Quick pointer, go to m Former one

2. Save the connection point and the inverted tail node

3. reverse m To n node

4. Splice the connection points and tail nodes

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) return null;

        ListNode cur = head;
        ListNode pre = null;
        while (m > 1) {
            pre = cur;
            cur = cur.next;
            m--;
            n--;
        }
        
        ListNode con = pre, tail = cur;
        while (n > 0) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
            n--;
        }
        
        if (con == null) {
            head = pre;
        }else {
            con.next = pre;
        }
        tail.next = cur;
        return head;

    }
}

Delete the last of the linked list N Nodes

Ideas ：1. Speed pointer Let's go first n Step 2. Go with the hands , Quick pointer to the last node , The slow pointer just goes to the previous node to delete the node 3. Delete node

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n == 0) return null;

        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode cur = pre;
        ListNode e = pre;
        // Quick pointer 
        while (n-- > 0) {
            e = e.next;
        }
        // Let the slow pointer go to the previous node to delete the node 
        while(e.next != null) {
            cur = cur.next;
            e = e.next;
        }
        cur.next = cur.next.next;
        return pre.next;
    }
}

Given a linked list , Return to the first node of the link where the list begins to enter .  If the list has no links , Then return to  null

Ideas ：

1. Speed pointer Come on, let's go at once 2 Step One step at a time  

2. When the fast and slow pointers meet , Description ring . Reset the fast pointer to head

3. The speed pointer moves every time 1 Step , When we meet again, it's the entry point

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode fast = head, slow = head;
        while (true) {
            // If there is no ring   End 
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            // The first time I met 
            if (fast == slow) break;
        }
        // Meet the general fast Reset to head
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        // The second encounter is the circular entry point 
        return slow;
    }
}

Addition of two numbers

Ideas

1. 2 A linked list Which is not empty sum += node.val

2. The value of the current node is sum %10

3. Save carry ,sum / 10

4. If the carry is not 0, You also need to create a new node .

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode res = new ListNode(-1);
        ListNode cur = res;
        int sum = 0;
        while (l1 != null || l2 != null || sum != 0) {
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            sum /= 10;
        }
        return res.next;
    }
}

Intersecting list

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       if (headA == null || headB == null) return null;
       ListNode a = headA;
       ListNode b = headB;
       while (a != b) {
           a = a== null ? headB : a.next;
           b = b == null ? headA : b.next;
       } 
       return a;
    }
}

Sort list

Ideas ：

1. The speed pointer finds the midpoint

2. Divide the linked list into 2

3. Recursive sort left , Sort right , And then merge

class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }
    private ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null)return head;
        ListNode tmp = new ListNode(Integer.MIN_VALUE);
        tmp.next = head;
        ListNode fast = tmp, slow = tmp;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode head2 = slow.next;
        slow.next = null;
        head  = mergeSort(head);
        head2 = mergeSort(head2);
        ListNode pre = tmp;
        while (head != null && head2 != null) {
            if (head.val < head2.val) {
                pre.next = head;
                pre = pre.next;
                head = head.next;
            }else {
                pre.next = head2;
                pre = pre.next;
                head2 = head2.next;
            }
        }
        if (head != null) {
            pre.next = head;
        }
        if (head2 != null) {
            pre.next = head2;
        }
        return tmp.next;
    }
}

Rotate the list

Ideas ：

1. First calculate the length of the linked list , If len % k == 0 There is no need to rotate .

2. Speed pointer , Let's go first k node , Slow hands start to walk

3. When the fast pointer reaches the tail node , Slow the pointer to the previous node to rotate

4. The next slow node is saved as the head node , The next setting of the slow node is null, The next of the tail node is connected to the head node .

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k <= 0) return head;
        int len = 0;
        ListNode tmp = head;
        while (tmp != null) {
            len++;
            tmp = tmp.next;
        }
        k = k % len;
        if (k == 0) return head;

        ListNode slow = head;
        ListNode fast = head;
        while (k-- > 0) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        ListNode res = slow.next;
        slow.next = null;
        fast.next = head;
        return res;
    }
}

Delete the duplicate elements of the sorting linked list

Ideas ：

1. Create virtual node

2. Speed pointer , The next value of the fast pointer is compared with the value of the current node , If equal, move back

3. Judge whether the next pointer of the slow pointer is the fast pointer , If it is a fast pointer , Then the slow pointer moves back

4. If not, then the next of the slow pointer = Next of the fast pointer

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if ( head == null) return head;
        ListNode dump = new ListNode (Integer.MIN_VALUE);
        dump.next = head;
        ListNode slow = dump;
        ListNode fast = head;
        while (fast != null) {
            while (fast.next != null && fast.next.val == fast.val) fast = fast.next;
            if (slow.next == fast) {
                slow = slow.next;
            }else {
                slow.next = fast.next;
            }
            fast = fast.next;
        }
        return dump.next;

    }
}

Odd and even list

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) return null;
        
        ListNode odd = head, even = head.next, evenHead = head.next;
        
        while (even != null && even.next != null) {
// Odd next is even next 
            odd.next = even.next;
// Odd number  =  Next in odd numbers   That is, the first even number, the next 
            odd = odd.next;
// Even next  =  The first even number, the next one, the next 
            even.next = odd.next;
// even numbers =  Even next 
            even = even.next;
        }
// The odd tail is followed by the even head node 
        odd.next = evenHead;
        return head;
    }
}