Summary of leetcode linked list problem solving skills

Recently, I have intensively painted a number of linked list questions , Here is a summary of problem-solving skills , And the corresponding problem solving ideas .

Problem solving ideas are not detailed , Mainly to summarize and classify , And hope to use a few words to inspire inspiration , Right should be a guide when you have no ideas and an outline when you review later .

There are also some classic topics that are important or always confused , The implementation logic of the code is also recorded here .

One 、 Two skills in solving linked list problems

Encountered linked list related problems , No matter what the problem is , First think about whether you can use the following two techniques .

1. The sentinel node

2. Double pointer

1、 The sentinel node

Sentry node is a very common linked list technique , In the scenario of dealing with the boundary problem of linked lists , It can reduce the complexity of our code . The main problems to be solved are as follows ：

1. After processing a linked list , You need to return the head node of the linked list . We started with the sentinel node （dummy）, Let it next The node points to head node . Last return Direct return dummy.next that will do .

2. When inserting or deleting nodes in the linked list , Using the sentinel node can simplify deletion head Node or direction head Processing logic when inserting nodes before .

3. When traversing a linked list , It may be necessary to record pre node . When you from head When the node starts traversal ,head It's not pre Node （ by null）. In this case, the sentry node is referenced , Equivalent to helping head The node initializes a pre node , It can be solved conveniently pre The node is empty .

Because the sentinel node is used in a wide range of scenarios , So here is not a targeted list of typical topics .

2、 Double pointer

The double pointer is so easy to use , In fact, it is not just a linked list , For array questions , It is also a very useful skill .

The main uses of double pointers are as follows ：

1. Two pointers walk on two linked lists

2. Speed pointer , Move forward at the same time

3. Front and back pointer , Go first n Step , Then the two pointers advance at the same time

Two pointers walk on two linked lists

Sometimes , You need to merge the two linked lists into one , Or split a linked list into two linked lists . here , You need to use two pointers to walk on the two linked lists , And process logic .

Typical topic ：

• 21. Merge two ordered lists ： Two pointers walk on two linked lists , Which pointer points to a node with a large value , Then put the node on the merged linked list , The pointer continues one step forward .

• 86. Separate the list ： According to the specified target value , Divide a linked list into two linked lists first . therefore , You need two pointers to walk on the two split linked lists . Then merge the two linked lists directly .

• 160. Intersecting list ： Two pointers walk on two linked lists , When a pointer points to the end of the current list , Continue to traverse another linked list . This ensures that when two pointers point to the same node , This node is the intersection node .

Speed pointer

A fast pointer is a slow pointer n times , When the fast pointer has finished , Where the slow pointer stays is the whole linked list 1/n It's about （ Approximate location ）. Generally speaking, the pointer moves one step slowly , Let's go two steps .

Typical topic ：

• 876. The middle node of a list ： Let's go two steps , Slow pointer one step . When the fast pointer reaches the end , Then the slow pointer is in the middle position .

• 141. Circular list ： Let's go two steps , Slow pointer one step . When the fast and slow hands meet , Start a slow pointer from the beginning , Two slow pointers go together , When we meet again , Is the entrance of the ring .

• 234. Palindrome list ： In fact, it is also the middle position of the linked list , Then judge whether it is palindrome . The logic of judging palindromes , With the help of stack or reverse the latter half of the linked list .

• 148. Sort list ： When using merge sort , It is also to find the intermediate node of each sub linked list through the speed pointer , To merge and deal with .

A pointer goes first n Step

Because there is no way to get the length of the linked list , For finding the penultimate n The problem of nodes , This method can traverse to find the target node .

Typical topic ：

• 19. Delete the last of the linked list N Nodes ： A pointer goes first n Step , Then both pointers go forward at the same time , When the first start pointer traversal is complete , The rear departure pointer is on the penultimate n Nodes .

• 61. Rotate the list ： Similar to the previous question , Just go first n Steps may exceed the total length of the linked list , It needs to take the mold for treatment .

Two 、 The solution of the classical linked list problem

Reverse a linked list

206. Reverse a linked list It is the most classic linked list problem . Except for advanced questions 92. Reverse a linked list II, Reverse linked list can also be used to solve other linked list questions , For example, as mentioned above 234. Palindrome list .

There are mainly two solutions to reverse linked list: recursive method and iterative method , Because it's easy to get dizzy when the pointer points around , So record the standard answer code here .

Recursive method

public ListNode reverseList(ListNode head) {
    //  This head It is the last node of the original linked list , It is also a new node of the inverted linked list 
    if (head == null || head.next == null) {
        return head;
    }
    //  Essentially ,resultNode Is recursion to the deepest point , The head node of the new linked list returned by one layer 
    ListNode resultNode = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return resultNode;
}

Iterative method

public ListNode reverseList(ListNode head) {
    ListNode current = head;
    ListNode pre = null;
    ListNode next;
    while (current != null) {
        next = current.next;
        current.next = pre;
        pre = current;
        current = next;
    }

    return pre;
}

LRU cache

146. LRU cache After all, it is a cache , It must be the structure of key value pairs , So we need HashMap.

And in reading and writing , Caching is required ： function get and put Must be O(1) The average time complexity of running .

In order to meet this requirement , The underlying data structure needs to be implemented with linked lists .

So we realized LRU The underlying data structure is ：HashMap + Linked list .

The code is as follows , Although not elegant , But it's easy to understand logic .

public class LRUCache {

    private int maxSize = 0;
    private Node head = new Node();
    private Node tail = head;
    HashMap<Integer, Node> map = new HashMap<>();

    public LRUCache(int capacity) {
        this.maxSize = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            // get This value is also used , Therefore, you need to update the value to the most recently used location 
            updateNode(node);
            return node.value;
        }

        return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            updateNode(node);
            return;
        }
        //  The newly inserted value is placed at the end of the chain 
        Node node = new Node(key, value);
        node.prev = tail;
        map.put(key, node);
        tail.next = node;
        tail = node;
        if (map.size() > maxSize) {
            //  At this point, you need to remove the longest unused data value 
            Node removed = head.next;
            head.next = removed.next;
            head.next.prev = head;
            map.remove(removed.key);
        }

    }

    private void updateNode(Node current) {
        //  If the current node is already the tail node , You don't need to move 
        if (current.next == null) {
            return;
        }
        //  The front node of the current node points to the back node of the current node , That is, delete the node from the original linked list 
        current.prev.next = current.next;
        current.next.prev = current.prev;
        //  Put the current node to the tail node 
        current.prev = tail;
        current.next = null;
        tail.next = current;
        //  Tail node movement 
        tail = current;
    }

    class Node {
        public int key;
        public int value;
        public Node prev;
        public Node next;
        public Node(){}
        public Node(int key,int value) {
            this.key = key;
            this.value = value;
        }
    }
}