leetcode - 237. Delete node in linked list
Please write a function to delete a specific node in the single linked list. When designing the function, you should pay attention to that you cannot access the head node of the linked list. You can only directly access the node to be deleted. The topic data ensures that the node to be deleted is not the end node.
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
leetcode - 83. Delete duplicate elements in the sorting linked list
Given the head of a sorted linked list, delete all duplicate elements so that each element appears only once. Returns the sorted linked list.
Method 1: use dummy node
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null){
return null;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = dummy;
while (cur.next!=null){
if(cur.val== cur.next.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return dummy.next;
}
}
The above solution will report an error because we have also calculated the value of dummy:
Therefore, we cannot use the value of dummy node:
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null){
return null;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = dummy;
while (cur.next!=null && cur.next.next!=null){
if(cur.next.val== cur.next.next.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return dummy.next;
}
}
Method 2: do not use dummy nodes, and in fact do not need to use dummy nodes, because you need to keep one node
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null){
return null;
}
ListNode cur = head;
while (cur.next!=null){
if(cur.val== cur.next.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return head;
}
}
leetcode - 234. Palindrome linked list
Give you the head node of a single linked list. Please judge whether the linked list is a palindrome linked list. If yes, return true; Otherwise, false is returned.
class Solution {
public boolean isPalindrome(ListNode head) {
if(head==null) return false;
// Find the intermediate node of the linked list
ListNode fast = head.next;
ListNode slow = head;
while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
ListNode head2 = slow.next;
// Reverse the second half of the linked list
head2 = reverseList(head2);
// Compare whether the linked list head and head2 are the same. The condition is head2= null
while (head2!=null){
if(head.val!=head2.val){
return false;
}
head = head.next;
head2 = head2.next;
}
return true;
}
private ListNode reverseList(ListNode cur) {
ListNode pre = null;
while (cur!=null){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
leetcode - 138. Copy linked list with random pointer
Give you a linked list with a length of n. each node contains an additional random pointer random, which can point to any node or empty node in the linked list.
Construct a deep copy of this linked list. The deep copy should consist of exactly n new nodes, in which the value of each new node is set to the value of its corresponding original node. The next pointer and random pointer of the new node should also point to the new node in the replication linked list, and these pointers in the original linked list and replication linked list can represent the same linked list state. The pointer in the copy linked list should not point to the node in the original linked list.
For example, if there are two nodes X and Y in the original linked list, where x.random -- > y. Then the corresponding two nodes X and Y in the copy linked list also have x.random -- > y. Returns the header node of the copy linked list.
A linked list composed of n nodes is used to represent the linked list in input / output. Each node is represented by a [val, random_index]:
Val: one represents node Integer of val.
random_index: the node index pointed by the random pointer (range from 0 to n-1); null if it does not point to any node.
Your code only accepts the head node of the original linked list as the incoming parameter.
Problem solving method: https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/liang-chong-shi-xian-tu-jie-138-fu-zhi-dai-sui-ji-/
We use hash table to solve this problem. First create a hash table, then traverse the original linked list, and put the original node as key and the new node as value into the hash table
The second step is to traverse the original linked list. This time, we need to set the next and random pointers of the new linked list
From the above figure, we can find that the original node and the new node are in one-to-one correspondence, so
map. Get (original node) and the corresponding new node is obtained
map. Get (original node. next) and get the corresponding new node next
map. Get (original node. random) and get the corresponding new node random
Therefore, we only need to traverse the original linked list again, and then set:
New node next -> map. Get (original node. next)
New node random -> map. Get (original node. random)
In this way, the next and random of the new linked list are connected in series
Finally, we then map Get (head), that is, the head node of the corresponding new linked list, can solve this problem.
class Solution {
public Node copyRandomList(Node head) {
// Create a hash table. key is the original node and value is the new node
HashMap<Node,Node> map = new HashMap<>();
Node cur = head;
// Put the original node and the new node into the hash table
while (cur!=null){
Node newNode = new Node(cur.val);
map.put(cur,newNode);
cur = cur.next;
}
// Traverse the original linked list and set the next and random of the new node
cur = head;
while (cur!=null){
Node newNode = map.get(cur);
if(cur.next!=null){
newNode.next = map.get(cur.next);
}
if(cur.random!=null){
newNode.random = map.get(cur.random);
}
cur = cur.next;
}
return map.get(head);
}
}
leetcode - 92. Reverse linked list II
Give you the head pointer of the single linked list and two integers left and right, where left < = right. Please reverse the linked list node from position left to position right and return the reversed linked list.
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if(head==null) return null;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode endNode = dummy;
// Let pre point to the previous node of the left position node
for(int i=0;i<left-1;i++){
pre = pre.next;
}
// Let the endNode point to the node in the right position
for(int i=0;i<right;i++){
endNode = endNode.next;
}
// Split the linked list and reverse the linked list from left to right
ListNode startNode = pre.next;
ListNode cur = endNode.next;
pre.next = null;
endNode.next = null;
// Reverse linked list
reverseList(startNode);
// Linked list
pre.next = endNode;
startNode.next = cur;
return dummy.next;
}
private void reverseList(ListNode cur) {
ListNode pre = null;
while (cur!=null){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
}
}
leetcode - 142. Circular linked list II
Given the head node of a linked list, it returns the first node from the linked list into the ring. If the linked list is acyclic, null is returned.
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null) return null;
ListNode fast = head;
ListNode slow = head;
while (true){
if(fast==null || fast.next==null){
return null;
}
fast = fast.next.next;
slow = slow.next;
if(slow==fast){
break;
}
}
slow = head;
while (slow!=fast){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
Sword finger Offer - 22 The penultimate node in the lin k ed list
Input a linked list and output the penultimate node in the linked list. In order to conform to the habit of most people, this question starts from 1, that is, the tail node of the linked list is the penultimate node.
For example, a linked list has six nodes. Starting from the beginning, their values are 1, 2, 3, 4, 5 and 6. The penultimate node of this linked list is the node with the value of 4.
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
if(head==null){
return null;
}
ListNode slow = head;
ListNode fast = head;
for(int i=0;i<k;i++){
fast = fast.next;
}
while (fast!=null){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
leetcode - 148. Sort linked list (merge sort algorithm)
Give you the head node of the linked list. Please arrange it in ascending order and return the sorted linked list.
Divide and Conquer: merge sorting algorithm
The merging method is a top-down merging method. Let the current interval of merging sorting be R[low... high], and the three steps of divide and conquer are:
① Decomposition: divide the current interval into two, that is, find the splitting point
② Solution: recursively merge and sort the two sub intervals R[low... Mid] and R[mid+1... high];
③ Combination: merge the sorted two sub intervals R[low... Mid] and R[mid+1... high] into an ordered interval R[low... high].
The end condition of recursion: the length of the subinterval is 1 (a record is naturally ordered).
class Solution {
public static void main(String[] args) {
int[] arr = {-3,1,2,3,4,5,6,10};
int left = 0;
int right = arr.length-1;
mergeSort(arr,left,right);
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
private static void mergeSort(int[] arr, int left, int right) {
if(left>=right){
return;
}
int mid = left+(right-left)/2;
mergeSort(arr,left,mid);
mergeSort(arr,mid+1,right);
merge(arr,left,mid,mid+1,right);
}
private static void merge(int[] arr, int leftStart, int leftEnd, int rightStart, int rightEnd) {
int i = leftStart;
int j = rightStart;
int k = 0;
int[] tmp = new int[leftEnd-leftStart+rightEnd-rightStart+2];
while (i<=leftEnd && j<=rightEnd){
if(arr[i]<=arr[j]){
tmp[k++] = arr[i++];
}else{
tmp[k++] = arr[j++];
}
}
while (i<=leftEnd){
tmp[k++] = arr[i++];
}
while (j<=rightEnd){
tmp[k++] = arr[j++];
}
k = leftStart;
for(int value:tmp){
arr[k++] = value;
}
}
}
Use the merge algorithm to solve this problem:
class Solution {
public ListNode sortList(ListNode head) {
// Empty linked list
if(head==null){
return null;
}
// Recursive termination condition
if(head.next==null){
return head;
}
// Split linked list
ListNode fast = head.next;
ListNode slow = head;
while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
ListNode head2 = slow.next;
slow.next = null;
ListNode list1 = sortList(head);
ListNode list2 = sortList(head2);
//Merge two linked lists
return mergeSortList(list1,list2);
}
private ListNode mergeSortList(ListNode head, ListNode head2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (head!=null && head2!=null){
if(head.val<head2.val){
cur.next = head;
head = head.next;
cur = cur.next;
}else {
cur.next = head2;
head2 = head2.next;
cur = cur.next;
}
}
if(head!=null){
cur.next = head;
}
if(head2!=null){
cur.next = head2;
}
return dummy.next;
}
}
leetcode - 23. Merge K ascending linked lists
Give you a linked list array, each linked list has been arranged in ascending order. Please merge all linked lists into an ascending linked list and return to the merged linked list.
Method 1: time complexity O (k^2*n), space complexity O(1)
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0){
return null;
}
ListNode ans = null;
for(int i=0;i<lists.length;i++){
ans = mergeTwoList(ans,lists[i]);
}
return ans;
}
private ListNode mergeTwoList(ListNode list1, ListNode list2) {
if(list1==null && list2==null){
return null;
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (list1!=null && list2!=null){
if(list1.val<list2.val){
cur.next = list1;
cur = cur.next;
list1 = list1.next;
}else{
cur.next = list2;
cur = cur.next;
list2 = list2.next;
}
}
if(list1!=null){
cur.next = list1;
}
if(list2!=null){
cur.next = list2;
}
return dummy.next;
}
}
Method 2: divide, rule and merge
The asymptotic time complexity is: O(kn) × logk).
Stack space recursion complexity: K
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null){
return null;
}
return merge(lists,0,lists.length-1);
}
private ListNode merge(ListNode[] lists, int left, int right) {
// branch
// Note this boundary condition: when left=right, lists[left] should be returned instead of null
// Boundary of sorting linked list: when head When next is null, head = should be returned instead of null
if(left==right){
return lists[left];
}
if(left>right){
return null;
}
int mid = left+(right-left)/2;
ListNode list1 = merge(lists,left,mid);
ListNode list2 = merge(lists,mid+1,right);
// close
return mergeList(lists,list1,list2);
}
private ListNode mergeList(ListNode[] lists, ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (list1!=null && list2!=null){
if(list1.val<list2.val){
cur.next = list1;
cur = cur.next;
list1 = list1.next;
}else{
cur.next = list2;
cur = cur.next;
list2 = list2.next;
}
}
if(list1!=null){
cur.next = list1;
}
if(list2!=null){
cur.next = list2;
}
return dummy.next;
}
}
leetcode - 24. Exchange the nodes in the linked list
Give you a linked list, exchange the adjacent nodes and return the head node of the linked list after exchange. You must complete this problem without modifying the value inside the node (that is, you can only exchange nodes).
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode start = head;
// 0--1--2
// 0--2--1
while (start!=null && start.next!=null){
ListNode end = start.next;
ListNode tmp = end.next;
pre.next = end;
end.next = start;
start.next = tmp;
pre = start;
start = tmp;
}
return dummy.next;
}
}
leetcode - 147. Insert and sort the linked list
Give the head of a linked list to the order, sort the linked list with insertion sort, and return the head of the sorted linked list.
Insert sorting algorithm:
Scan every element from scratch. Whenever an element is scanned, it is inserted into the appropriate position of the head to keep the head data in order
If it is the insertion sort of the array, the front part of the array is an ordered sequence. Each time you find the insertion position of the first element (element to be inserted) behind the ordered sequence, move the elements behind the insertion position in the ordered sequence one bit back, and then place the element to be inserted in the insertion position.
class Solution {
public static void main(String[] args) {
int[] arr = {1,9,5,2,9,3};
insertSort(arr);
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
private static void insertSort(int[] arr) {
for(int i=1;i<arr.length;i++){
int insertValue = arr[i];
int insertIndex = i-1;
while (insertIndex>=0 && insertValue<=arr[insertIndex]){
arr[insertIndex+1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex+1] = insertValue;
}
}
}
The insertion sorting algorithm is used to solve this problem:
For the linked list, when inserting elements, you only need to update the pointers of adjacent nodes, and you don't need to move the elements behind the insertion position backward like an array. Therefore, the time complexity of the insertion operation is O(1), but finding the insertion position requires traversing the nodes in the linked list. The time complexity is O(n), so the total time complexity of the insertion sorting of the linked list is still O(n^2), Where n is the length of the linked list.
class Solution {
public ListNode insertionSortList(ListNode head) {
if(head==null){
return null;
}
// 1 2 7 4 0 5
ListNode dummy = new ListNode(0);
dummy.next = head;
// Last executes the last node of the ordered linked list
ListNode last = head;
// cur points to the node to be sorted
ListNode cur = last.next;
while (cur!=null){
if(last.val<cur.val){
last = last.next;
cur = cur.next;
}else{
last.next = cur.next;
// Use a pointer pre to find the position of the node to be inserted
ListNode pre = dummy;
while (pre.next.val<cur.val){
pre = pre.next;
}
cur.next = pre.next;
pre.next = cur;
cur = last.next;
}
}
return dummy.next;
}
}
leetcode - 148. Sorting linked list (insert sorting algorithm)
Give you the head node of the linked list. Please arrange it in ascending order and return the sorted linked list.
Insert sorting algorithm:
class Solution {
public ListNode sortList(ListNode head){
if(head==null){
return null;
}
// 1 2 7 4 0 5
ListNode dummy = new ListNode(0);
dummy.next = head;
// Last executes the last node of the ordered linked list
ListNode last = head;
// cur points to the node to be sorted
ListNode cur = last.next;
while (cur!=null){
if(last.val<cur.val){
last = last.next;
cur = cur.next;
}else{
last.next = cur.next;
// Use a pointer pre to find the position of the node to be inserted
ListNode pre = dummy;
while (pre.next.val<cur.val){
pre = pre.next;
}
cur.next = pre.next;
pre.next = cur;
cur = last.next;
}
}
return dummy.next;
}
}
leetcode - 86. Separate linked list
Give you a head node of the linked list and a specific value X. please separate the linked list so that all nodes less than x appear before nodes greater than or equal to X. You should keep the initial relative position of each node in both partitions.
class Solution {
public ListNode partition(ListNode head, int x) {
if(head==null){
return null;
}
// Define two dummy nodes and divide the linked list into two linked lists, one is greater than or equal to X and the other is less than x
// cur is used to traverse the linked list nodes and compare with x
ListNode cur = head;
ListNode largeNode = new ListNode(-1);
ListNode smallNode = new ListNode(-1);
ListNode small = smallNode;
ListNode large = largeNode;
while (cur!=null){
if(cur.val<x){
small.next = cur;
small = small.next;
cur = cur.next;
}else{
large.next = cur;
large = large.next;
cur = cur.next;
}
}
large.next = null;
small.next = largeNode.next;
return smallNode.next;
}
}
leetcode - 61. Rotating linked list
Give you a head node of the linked list. Rotate the linked list and move each node of the linked list k positions to the right.
Method 1:
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head==null){
return null;
}
// First, let the tail of the linked list point to the head to form a ring, find the last k node, and disconnect the previous node
ListNode fast = head;
ListNode slow = head;
// Find the length of the linked list
int n = 0;
while (fast!=null){
n++;
fast = fast.next;
}
// The reason for this is that k > n exists
k = k % n;
// Find the previous node of the penultimate node
fast = head;
for(int i=0;i<k;i++){
fast = fast.next;
}
while (fast.next!=null){
fast = fast.next;
slow = slow.next;
}
// Connect the tail of the linked list with the head
fast.next = head;
// Disconnect from the previous node of the penultimate node
ListNode tmp = slow.next;
slow.next = null;
return tmp;
}
}
Method 2:
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head==null){
return null;
}
// First, let the tail of the linked list point to the head to form a ring, find the last k node, and disconnect the previous node
ListNode cur = head;
// Find the length of the linked list
int n = 1;
while (cur.next != null) {
cur = cur.next;
n++;
}
// Connect the tail and head of the linked list
cur.next = head;
// Find the previous node of the penultimate node
k = n-k%n;
for(int i=0;i<k;i++){
cur = cur.next;
}
ListNode tmp = cur.next;
cur.next = null;
return tmp;
}
}
leetcode - 328. Parity linked list
Give the head node of the order linked list, combine all nodes with odd index and even index respectively, and then return the reordered list. The index of the first node is considered to be odd, the index of the second node is even, and so on.
Note that the relative order within even and odd groups should be the same as when entering. You have to solve this problem under the additional space complexity of O(1) and the time complexity of O(n).
Method 1: the idea I used in this question is the same as the idea separated by 86 questions. For the optimization method, see method 2
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head==null){
return null;
}
ListNode oddNode = new ListNode(0);
ListNode evenNode = new ListNode(0);
ListNode odd = oddNode;
ListNode even = evenNode;
ListNode cur = head;
int count = 1;
while (cur!=null){
if(count%2==1){
odd.next = cur;
cur = cur.next;
odd = odd.next;
count++;
}else{
even.next = cur;
cur = cur.next;
even = even.next;
count++;
}
}
// There are even number of linked list nodes
if(odd.next!=null){
odd.next = null;
}
// There are an odd number of linked list nodes
if(even.next!=null){
even.next=null;
}
odd.next = evenNode.next;
return oddNode.next;
}
}
Method 2: merge after separating nodes (the idea is the same as method 1, which is the optimization of method 1)
For the original linked list, each node is an odd or even node. The head node is an odd node, the last node of the head node is an even node, and the parity of adjacent nodes is different. Therefore, odd nodes and even nodes can be separated into odd linked list and even linked list, and then the even linked list is connected after the odd linked list, and the combined linked list is the result linked list.
The head node of the original linked list is also the head node of the odd linked list and the head node of the result linked list. The latter node of the head is the head node of the even linked list. Make evenHead = head Next, then evenHead is the head node of the even linked list.
Maintain two pointers, odd and even, pointing to odd and even nodes respectively. Initially, odd = head and even = evenHead. The odd and even nodes are separated into two linked lists by iteration. In each step, the odd nodes are updated first, and then the even nodes are updated.
- When updating odd nodes, the latter node of odd nodes needs to point to the latter node of even nodes, so make odd next = even. Next, and then make odd = odd Next, at this time, odd becomes the next node of even.
- When updating even nodes, the latter node of even nodes needs to point to the latter node of odd nodes, so make even next = odd. Next, and then make even = even Next, at this time, even becomes the next node of odd.
After the above operation, the separation of an odd node and an even node is completed. Repeat the above operation until all nodes are separated. The condition that all nodes are separated is that even is an empty node or even Next is an empty node. In this case, odd points to the last odd node (that is, the last node of the odd linked list).
Finally, make odd Next = evenhead. After connecting the even linked list to the odd linked list, the odd linked list and even linked list are merged. As a result, the head node of the linked list is still head.
The idea seems very complex. It's better to understand the code. In fact, it's very simple:
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head==null){
return null;
}
ListNode odd = head;
ListNode evenHead = head.next;
ListNode even = evenHead;
// When the number of linked list nodes is odd, it is even next!= null
// When the number of linked list nodes is even, yes (even!=null)
while (even!=null && even.next!=null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
leetcode - 2. Addition of two numbers (summation of linked list)
Give you two non empty linked lists to represent two non negative integers. They store each number in reverse order, and each node can store only one number. Please add the two numbers and return a linked list representing sum in the same form. You can assume that neither number starts with 0 except the number 0.
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
/**
* 9 9 9 9 9 9 9
* + 9 9 9 9 0 0 0
* ------------------------------
* 8 9 9 9 0 0 0 1
*/
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int sum = 0;
while (l1!=null || l2!=null){
if(l1!=null){
sum = sum+l1.val;
l1 = l1.next;
}
if(l2!=null){
sum = sum + l2.val;
l2 = l2.next;
}
cur.next = new ListNode(sum%10);
cur = cur.next;
sum = sum / 10;
}
if(sum==1){
cur.next = new ListNode(1);
}
return dummy.next;
}
}
Sword finger Offer - 06 Print linked list from end to end
Enter the head node of a linked list, and return the value of each node from tail to head (returned by array).
class Solution {
public int[] reversePrint(ListNode head) {
if(head==null){
return new int[]{};
}
ListNode cur = head;
Stack<Integer> stack = new Stack<>();
while (cur!=null){
stack.push(cur.val);
cur = cur.next;
}
int[] arr = new int[stack.size()];
for(int i=0;i<arr.length;i++){
arr[i] = stack.pop();
}
return arr;
}
}