[interview brush 101] linked list

Abstract

【 Interview must brush 101】 series blog The purpose is to summarize the interview must brush 101 Interesting in 、 Exercises that may be tested in the interview . Summarize the general problem-solving methods , Summarize ideas for special exercises . It is written for your review , I also hope to communicate with you .

【 Interview must brush 101】 recursive / Backtracking algorithm summary I（ Ten minutes to understand the backtracking algorithm ）
【 Interview must brush 101】 recursive / Backtracking algorithm summary II（ Ten minute backtracking algorithm problem ）

1 Basic knowledge of linked list

Single chain list

public class ListNode {
    
    int val;
    ListNode next = null;
    
    ListNode(int val) {
    
        this.val = val;
    }
}

Double linked list

public class ListNode {
    
    int val;
    ListNode next = null;
    ListNode pre = null;
    ListNode(int val) {
    
        this.val = val;
    }
}

There are few problems like linked list , Just pay attention to the following questions .

2 The interview must brush exercises

2.1 k A set of reverse linked list

Common reverse linked list ：

A very simple picture , It refers to the current node to the previous node , Then turn the current node into the next node to traverse .

import java.util.*;
public class Solution {
    
public class Solution {
    
    public ListNode ReverseList(ListNode cur) {
    
        ListNode pre = null;
        ListNode next = null;
        while (cur != null) {
    
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

Then look at the linked list Every time k A group of nodes is flipped .

First, it can be realized by recursion ： Every time k In fact, a group can do the latter first and then the front , Big problems consist of many small problems .
Then small problems can be solved by simply flipping the linked list . See code for details , It's worth learning .

import java.util.*;
public class Solution {
    
    public ListNode reverseKGroup (ListNode head, int k) {
    
        if (head == null || head.next == null) return head;
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
    
            if (tail == null) {
    
                return head;
            }
            tail = tail.next;
        }
        //  Before turning over k Elements 
        ListNode newHead = reverse(head, tail);
        // head It's the last element . This recursion is very spiritual .
        head.next = reverseKGroup(tail, k);
        return newHead;
    }
    //  reverse [head, tail)
    public ListNode reverse (ListNode cur, ListNode tail) {
    
        ListNode pre = null;
        ListNode next = null;
        while (cur != tail) {
    
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

2.2 Merge k A linked list

Topic link ：BM5 Merge k Sorted linked list

Why is this problem worth doing ？ There are three main inspection points ：

• What is the merger strategy ？ be based on Merge sort Two by two consolidation of ; Priority queue .
• How to merge two ordered linked lists ？ Build a Head node , Insert whoever is young .

import java.util.*;
public class Solution {
    
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
    
        return mergeList(lists, 0, lists.size() - 1);
    }
    
    public ListNode mergeList(ArrayList<ListNode> list, int l, int r) {
    
        if (l== r) {
    
            return list.get(l);
        }
        if (l > r) {
    
            return null;
        }
        int mid = l + ((r - l) >> 1);
        ListNode left = mergeList(list, l, mid);
        ListNode right = mergeList(list, mid + 1, r);
        return merge2Lists(left, right);
    }
    
    //  Merge two linked lists 
    public ListNode merge2Lists(ListNode list1, ListNode list2) {
    
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (list1 != null && list2 != null) {
    
            if (list1.val > list2.val) {
    
                cur.next = list2;
                list2 = list2.next;
            } else {
    
                cur.next = list1;
                list1 = list1.next;
            }
            cur = cur.next;
        }
        if (list1 != null) cur.next = list1;
        if (list2 != null) cur.next = list2;
        return head.next;
    }
}

2.3 Add the linked list

Topic link ： Add the linked list （ Two ）

At first glance, it seems so difficult ？ Where to start adding ？ Unclear . Why not , Because from next Node Can't find pre Node, This is the characteristic of single linked list . however , If you turn it over, you can do it well .

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; * } */

public class Solution {
    
    /** * * @param head1 ListNode class  * @param head2 ListNode class  * @return ListNode class  */
    public ListNode addInList (ListNode head1, ListNode head2) {
    
        ListNode h1 = reverse(head1);
        ListNode h2 = reverse(head2);
        int tag = 0;
        int val = 0;
        ListNode cur = null, pre = null;
        while (h1 != null || h2 != null) {
    
            if (h1 != null) {
    
                val += h1.val;
                h1 = h1.next;
            }
            if (h2 != null) {
    
                val += h2.val;
                h2 = h2.next;
            }
            val += tag;
            if (val >= 10) {
    
                tag = 1;
                val = val % 10;
            } else {
    
                tag = 0;
            }
            cur = new ListNode(val);
            val = 0;
            cur.next = pre;
            pre = cur;
        }
        if (tag == 1) {
    
            cur = new ListNode(1);
            cur.next = pre;
        }
        return cur;
    }
    
    public ListNode reverse (ListNode cur) {
    
        ListNode pre = null;
        ListNode next = null;
        while (cur != null) {
    
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

2.4 The sort of single linked list

Topic link ：BM12 The sort of single linked list .

2.5 Judge whether a linked list is palindrome structure

2.6 Delete duplicate elements of linked list