This article mainly explains the linked list correlation algorithm;
This topic Describes the ListNode node
First of all, let’s introduce the node class of the linked list we used in this paper. The main purpose of this linked list is to solve the problems related to Leetcode, so the node does not use generics, but directly uses int. If you are defining a data structure, you need to use generics to store node information.
Four constructors, no arguments, one argument, two arguments, and a constructor that converts an array to a linked list; Overriding toString prints the elements in the list;
public class ListNode {
int val;
ListNode next;
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
public ListNode(int[] arr){
this.val = arr[0];
ListNode cur = this;
for (int i = 1; i < arr.length; i++) {
cur.next = new ListNode(arr[i]);
cur = cur.next;
}
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("list: ");
ListNode cur = this;
while (cur!= null){
builder.append(cur.val).append(" -> ");
cur = cur.next;
}
builder.append("null");
return builder.toString();
}
}
Copy the code1. Leetcode19 — Delete the NTH node from the list
Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.
Advanced: Can you try using a scan implementation? For example: input: head = [1,2,3,4,5], n = 2 output: [1,2,3,5]
This can scan the linked list first, record how many nodes, and then the penultimate NTH node can be converted into a positive number of nodes, and then you can find the nodes to be deleted through traversal can be deleted; However, the problem requires us to walk through the list only once, so we can use the two-pointer technique;
We first define the virtual head node, and make the next of the virtual head node point to head. Then we define the fast and slow Pointers to point to the virtual head node, and make the fast pointer advance n nodes earlier, and then make the fast and slow Pointers advance at the same time. When the fast pointer reaches the end of the linked list, the slow pointer just reaches the node before the node to be deleted. At this point, we can operate next of the slow node to point to next of the slow node. In this way, the operation of traversing the linked list can be deleted; Finally, we need to return dummyhead. next instead of head. The two expressions ostensibly mean the same thing, but it is possible that head has been deleted.
Public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummyHead = new ListNode(); dummyHead.next = head; ListNode faster = dummyHead; ListNode slower = dummyHead; for (int i = 0; i < n + 1; i++) { faster = faster.next; } while (faster ! = null) { faster = faster.next; slower = slower.next; } slower.next = slower.next.next; return dummyHead.next; }Copy the codeLeetcode206 — Reverse linked list
Given the head node of a single linked list, reverse the list and return the reversed list.
Input: head = [1,2,3,4,5] output: [5,4,3,2,1]
Reverse linked list can be said to be the more classical algorithm problem of linked list, can be solved by two methods, respectively is iteration and recursion;
The iterative solution is as follows: Pre represents the previous node of the current node, cur represents the current node, and next represents the next node of the current node. The next node of cur points to pre, pre points to cur, cur points to Next, and the loop continues until cur==null. If there is no next, there is no node.
Solution one iteration
Public ListNode reverseList(ListNode head) {ListNode pre = null; ListNode pre = null; ListNode pre = null; ListNode cur = head; while (cur ! = null) { ListNode next = cur.next; Cur. Next = pre; pre = cur; cur = next; } return pre; }Copy the codeThe recursive solution is as follows: first, define the recursive termination condition, and return if the current node or the next node of the current node is NULL. We then recursively call the current function passing in the next node of the head as an argument and logging the return value; Next = head; next = null; next = null; head. Next = null;
Solution binary recursion
/ / leetcode 206 inversion list public ListNode reverseList (ListNode head) {/ / recursive termination conditions the if (head = = null | | head. The next = = null) { return head; } // ListNode pHead = reverseList(head.next); // Head. Next. Next = head; head.next = null; return pHead; }Copy the code3. Leetcode203 — Removes elements from the list
Val == val; delete all nodes in the list where node. val == val and return the new head Node.
For example: input: head =,2,6,3,4,5,6 [1], val = 6 output: [1, 2, 3, 4, 5]
The iterative solution is as follows: first create a virtual head node with next pointing to the head node, and then create a pre node pointing to the virtual head node as long as pre-.next! Val = val, pre. Next = val, pre. Next = pre. Next = next. Otherwise, let pre = pre. Next proceed to the judgment of the next node; Finally, return dummyhead. next, not head;
Solution – Iterative solution
// Leetcode 203 removes iterated elements from the list, Public ListNode removeElements(ListNode head, int val) {ListNode dummyHead = new ListNode(); dummyHead.next = head; ListNode pre = dummyHead; while (pre.next ! = null) { if (pre.next.val == val) { pre.next = pre.next.next; } else { pre = pre.next; } } return dummyHead.next; }Copy the codeSolution Method two recursive solution
Val = val, head is the node to be deleted. Head points to head. Next and returns head. That’s the whole recursion;
Public ListNode removeElements(ListNode head, Int val) {if (head == null) {return null; Next = removeElements(head. Next, val); if (head.val == val) { head = head.next; } return head; }Copy the codeLeetcode24 — Swap nodes in linked lists in pairs
Given a linked list, swap adjacent nodes in pairs and return the swapped list.
You can’t just change the values inside a node, you need to actually swap nodes. Input: head = [1,2,3,4] output: [2,1,4,3]
The solution is as follows. First, define the termination condition for recursion. Since two nodes need to be swapped, it is obvious to stop recursion when head or head.next is empty.
To recurse, first save the next node of the current head; Call next recursively, passing in the next node of next, which swaps the next pair of nodes, and assign the returned node to the next node of head. Finally, the next of the previously saved next node points to the head, which completes the pair swap, and finally returns to next.
/ / leetcode24 two switching nodes in the list of public ListNode swapPairs (ListNode head) {/ / recursive termination conditions the if (head = = null | | head. The next = = null) { return head; } ListNode next = head. Next; ListNode next = head. head.next = swapPairs(next.next); next.next = head; return next; }Copy the code5. Turn arrays into linked lists
Next = new ListNode(arr[I]); cur.next = new ListNode(arr[I]) Cur = cur.next to proceed to the next element;
/ / array to list public ListNode convertArrayToListNode (int [] arr) {if (arr = = null | | arr. Length = = 0) {return null; } ListNode head = new ListNode(arr[0]); ListNode cur = head; for (int i = 1; i < arr.length; i++) { cur.next = new ListNode(arr[i]); cur = cur.next; } return head; }Copy the code6. Leetcode141 — Determine if the list is a circular list
Given a linked list, determine whether there are rings in the list. Returns true if there are rings in the list. Otherwise, return false.
If there is a node in the list that can be reached again by continuously following the next pointer, then there is a ring in the list.
If the fast and slow nodes collide, the linked list is circular. If the fast and slow nodes end, the linked list is not circular. If the fast and slow nodes end, the linked list is not circular.
Public Boolean hasCycle(ListNode head) {ListNode fast = head; public Boolean hasCycle(ListNode head) {ListNode fast = head; ListNode slow = head; while (fast ! = null && fast.next ! = null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { return true; } } return false; }Copy the codeLeetcode142 — Returns the entry point of the circular list
Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.
If there is a ring, you need to ask the first node to access the ring. Create a Boolean variable isCycle to indicate whether there is a ring. If there is a ring, set it to true. If there is a ring, reset the fast node or slow node to head after the collision, and then let the fast node and slow node move forward step by step at the same speed. Either of the fast or slow nodes can be returned; Return NULL if there is no loop;
Public ListNode detectCycle(ListNode head) {ListNode fast = head; ListNode detectCycle(ListNode head) {ListNode fast = head; ListNode slow = head; boolean isCycle = false; while (fast ! = null && fast.next ! = null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { isCycle = true; break; } } slow = head; if (isCycle){ while (fast ! = slow) { fast = fast.next; slow = slow.next; } return slow; }else { return null; }}Copy the codeSource:
Source: LeetCode link: leetcode-cn.com/problemset/…