One-way linked list:

Each node is a collection of information, including the element itself and the address of the next node.

Linked lists can have headers or no headers. The difference is that linked lists with headers waste space, but are easy to understand, easy to handle, and hard to make mistakes

Defines singly linked lists and their operations

Public class SingleList {// Define a Node inner class class Node{int data; Node next; public Node(int data){ this.data = data; }} public Node head; // Current Node, easy to add and traversal operations (traversal the list through the current Node) public Node current; Public void add(int data){if(head == null){head = new Node(data); current = head; }else{// Put new Node after current Node. Next = new Node(data); // Current = current. Next; Public void print(node node){if(node == null){return; } current = node; while(current ! = null){ System.out.println(current.data); current=current.next; } } public static void main(String[] args) { SingleList list = new SingleList(); list.add(1); list.add(2); list.add(3); list.print(list.head); }}Copy the code

How to convert arrays to linked lists:

Using the first element of the array as the head node of the linked list, current starts equal to the head node, and the loop goes through, assigning the value of the array to the node, which points to the new node, and which is then treated as the current node

public Node arrayToList(int[] arr){ if(arr.length==0){ return null; } Node head = new Node(arr[0]); Node current=head; for(int i=1; i<arr.length; i++){ Node node =new Node(arr[i]); current.next=node; current=node; } return head; }Copy the code

Here are some algorithms:

Example 1: Find the KTH to last node in a singly linked list

Idea 1: Let’s iterate over the length n of the list, with the KTH node in the position n-k+1

public Node FindKthToTail (Node head, int k) { int n=0; current = head; While (current. Next! =null){ n++; current=current.next; } current=head; for(int i=0; i<n-k+1; i++){ current=current.next; } return current; }Copy the code

When the fast pointer moves to the KTH node, the fast and slow Pointers move backward at the same time. When the fast pointer reaches the last node, the slow pointer points to the KTH node from the last

public Node FindKthToTail (Node head, int k) { Node slow=head; Node fast=head; for(int i=1; i<k; i++){ fast=fast.next; } while(fast.next! =null){ fast=fast.next; slow=slow.next; } return slow; }Copy the code

Example 2: List inversion

Idea 1: Use recursion

    public Node ReverseList(Node head) {
        if(head==null || head.next==null){
            return head;
        }
        Node nextNode = head.next;
        Node newHead = ReverseList(nextNode);
        nextNode.next=head;
        head.next=null;
        return newHead;
    }
Copy the code

Idea 2: Define a pointer before and after, and reverse the pointer before and after

public Node ReverseList(Node head) { if(head==null || head.next==null){ return head; } Node pre=head; Node current=head.next; Node temp; while(current! =null){ temp=current.next; current.next=pre; pre=current; current=temp; } head.next=null; return pre; }Copy the code

Example 3: Circular linked lists

Check whether the linked list has rings: set two fast and slow Pointers, the slow pointer moves at speed 1, the fast pointer moves at speed 2. If the fast and slow Pointers meet, the linked list has a ring

public boolean hasCycle(Node head){ if(head==null || head.next==null){ return false; } Node slow=head; Node fast=head; while(true){ if(fast==null || fast.next==null){ return false; } slow=slow.next; fast=fast.next.next; if(slow==fast){ return true; }}}Copy the code

Find the entry node of the circular list:

After the first encounter, let fast point to the head node again, then fast and slow move at the same speed, the second encounter, this node is the entry node

This problem is a little bit convoluted, so I won’t write the solution

public Node EntryNodeOfLoop(Node head){ if(head==null || head.next==null){ return null; } Node slow=head; Node fast=head; while(true){ if(fast==null || fast.next==null){ return null; } slow=slow.next; fast=fast.next.next; if(slow==fast){ break; } } fast=head; while(true){ slow=slow.next; fast=fast.next; if(slow==fast) { return slow; }}}Copy the code

Example problem 4: Merge two sorted linked lists

Recursion: Find the smaller head of the two lists, which points to the smaller number

public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null){ return list2; } if(list2==null){ return list1; } if(list1.val<list2.val){ list1.next=Merge(list1.next,list2); return list1; }else{ list2.next=Merge(list1,list2.next); return list2; }}Copy the code

Use a new list to save the sorted list

public ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) { return list2; } if (list2 == null) { return list1; } ListNode head = new ListNode(-1); ListNode list3 = head; while (list1 ! = null && list2 ! = null) { if (list1.val < list2.val) { list3.next = list1; list1 = list1.next; } else { list3.next = list2; list2 = list2.next; } list3 = list3.next; } while (list1 ! = null) { list3.next = list1; list1 = list1.next; list3 = list3.next; } while (list2 ! = null) { list3.next = list2; list2 = list2.next; list3 = list3.next; } return head.next; }Copy the code