Linked list basic algorithm problem

Definition of linked list (java)

//Definition of single linked list
public class ListNode{
	int val;
	ListNode next;	//Point to next node
	ListNode(){};	//Nonparametric structure
	ListNode(int val){ this.val=val; }
	ListNode(int val,ListNode next){ this.val=val; this.next=next; }
}

1. Remove linked list elements

https://leetcode-cn.com/problems/remove-linked-list-elements/
Give you a head node of the linked list and an integer val. please delete all nodes in the linked list that meet the requirements Val = = Val's node and returns a new header node.

Example 1:
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:
Input: head = [7,7,7,7], val = 7
Output: []

Method 1: direct method - iteration
Consider when deleting header nodes

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while(head!=null && head.val==val){
            head=head.next;     //If the conditions are met, move the position of the head node
        }
        if(head==null) return head;
        ListNode first = head;  //Save the location of the header node
        while(head.next!=null){
            if(head.next.val==val){
                head.next=head.next.next;
            }else{
                head=head.next;
            }
        }
        return first;
    }
}
//Time complexity: O(n)
//Space complexity: O(1)

Method 2: virtual head node (common)
Set a virtual head node without considering the head node, so that all nodes in the original linked list can be removed in a unified way

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //Virtual node, pointing to the next node is the head node
        ListNode dummy = new ListNode(-1,head); 
        ListNode prev=dummy;    //Borrow other nodes for deletion to ensure dummy Next points to the header node
        while(prev.next!=null){
            if(prev.next.val==val){
                prev.next=prev.next.next;
            }else{
                prev=prev.next;
            }
        }
        return dummy.next;
    }
}
//Time complexity: O(n)
//Space complexity: O(1)

Method 3: recursion
The termination condition of recursion is that the head is empty. In this case, the head is returned directly.
When the head is not empty, delete it recursively, then judge whether the node value of the head is equal to val and decide whether to delete the head.

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;	//Exit recursion
        }
        head.next = removeElements(head.next, val);	//The next node is handed over to recursive processing
        return head.val == val ? head.next : head;	//Ensure that the current node meets the conditions
    }
}
//Time complexity: O(n)
//Spatial complexity: O(n), where n is the length of the linked list. The space complexity mainly depends on the recursive call stack, which will not exceed n layers at most

2. Design linked list

https://leetcode-cn.com/problems/design-linked-list/
Design the implementation of linked list. You can choose to use single linked list or double linked list. A node in a single linked list should have two attributes: val and next. val is the value of the current node, and next is the pointer / reference to the next node. If you want to use a two-way linked list, you also need an attribute prev to indicate the previous node in the linked list. It is assumed that all nodes in the linked list are 0-index.

Implement these functions in the linked list class:

• get(index): get the value of the index node in the linked list. Returns - 1 if the index is invalid.
• addAtHead(val): add a node with value val before the first element of the linked list. After insertion, the new node will become the first node in the linked list.
• addAtTail(val): append the node with value val to the last element of the linked list.
• addAtIndex(index,val): add a node with value val before the index node in the linked list. If the index is equal to the length of the linked list, the node will be attached to the end of the linked list. If the index is greater than the length of the linked list, the node will not be inserted. If the index is less than 0, the node is inserted in the header.
• Delete atindex (index): if the index is valid, delete the index node in the linked list.

Method 1: single linked list method
Design addAtIndex first. Because of the relationship between pseudo headers, addatahead and addatatail can be completed by using addAtIndex.

public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}

class MyLinkedList {

    int size;   //Linked list size
    ListNode head;  //Virtual head node

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }
   
    /*+++++++++++++++++Method implementation++++++++++++++++++*/
    
    //Insert new node corresponding to subscript
    public void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;
        ListNode node = new ListNode(val);
        ListNode prev = head;
        while(index-- > 0) prev = prev.next;
        node.next = prev.next;
        prev.next = node;
        size++;
    }
	//Insert new node in header
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    //Insert new node at tail
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    //Delete the node corresponding to the subscript
    public void deleteAtIndex(int index) {
        if(index>=size||index<0) return;
        ListNode prev=head;
        while(index-- > 0) prev = prev.next;
        prev.next = prev.next.next;     //Delete node prev next
        size--;
    }
	//Get the node value of the corresponding subscript
    public int get(int index) {
        if(index>=size||index<0) return-1;
        ListNode prev=head;
        while(index-- >= 0) prev = prev.next;
        return prev.val;
    }
}

3. Reverse linked list

https://leetcode-cn.com/problems/reverse-linked-list/
Give you the head node of the single linked list. Please reverse the linked list and return the reversed linked list.

Solution:
Suppose there is a linked list 1 → 2 → 3 →∅, we want to change it to ∅← 1 ← 2 ← 3.
Method 1: iteration
When traversing the list, change the next pointer of the current node to point to the previous element. Since a node does not reference its previous node, its previous element must be stored in advance. Another pointer tmp is needed to store the next node before changing the reference. Don't forget to return a new header reference at the end!

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode curr=head;
        while(curr!=null){
            ListNode tmp=curr.next; // Save next node
            curr.next=pre;  //Point reverse
            pre=curr;
            curr=tmp;
        }
        return pre;     //Returns the new header node
    }
}
//Time complexity: O(n)
//Space complexity: O(1) 

Method 2: recursion

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;  //Point to reverse head next-->head
        head.next = null;       // Current head -- > null
        return p;
    }
}
//Time complexity: O(n)
//Space complexity: O(n) 

4. Exchange the nodes in the linked list

https://leetcode-cn.com/problems/swap-nodes-in-pairs/
Given a linked list, two adjacent nodes are exchanged, and the exchanged linked list is returned.
You can't just change the value inside the node, but you need to actually exchange nodes.

Input: head = [1,2,3,4]
Output: [2,1,4,3]
Solution:
Method 1: iterative method
Specifically, the node relationship before the exchange is temp - > node1 - > node2. After the exchange, the node relationship will become temp - > node2 - > node1. Therefore, the following operations are required

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);   //Virtual head node
        dummy.next = head;
        ListNode prev = dummy;
        while(prev.next!=null && prev.next.next!=null){
            ListNode temp = head.next.next; // Cache next
            prev.next = head.next;          // Change the next of prev to the next of head
            head.next.next = head;          // Put head The next of next (prev. Next) points to head
            head.next = temp;               // Connect the next of head to the cached temp
            prev = head;                    // Step 1 bit
            head = head.next;               // Step 1 bit
        }

        return dummy.next;
    }
}
//Time complexity: O(n)
//Space complexity: O(1) 

5. Delete the penultimate node of the linked list

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list. (1 <= n <= sz)
Can you try using one scan implementation?
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Idea: double pointer
For the classic application of double pointer, if you want to delete the penultimate node, let fast move n steps, and then let fast and slow move at the same time until fast points to the end of the linked list. Delete the node pointed to by slow.
Here, when fast points to null, slow points to the precursor node to be deleted, and directly slow next=slow. next. Next delete the node.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);  //Virtual head node
        ListNode fast = head;   //Quick pointer
        ListNode slow = dummy;   //Slow pointer
        while(n-->0){
                fast=fast.next;     //The fast pointer moves n steps first
        }
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;     //Delete Vertex 
        return dummy.next;
    }
}