Classification brush algorithm, adhere to, progress!
Brush the route reference: github.com/youngyangya…
Github.com/chefyuan/al…
List based
Before we start brushing up, we’d better understand the basics of linked lists, so now, let’s get started.
A linked list is a linear list that is stored in a chain and does not require that data elements that are logically adjacent are also physically adjacent.
Singly linked lists
A one-way linked list contains two values: the value of the current node and a reference to the next node. They can also be called data fields and pointer fields.
The entry node is called the head node, and the last node points to null.
As shown in the figure:
Double linked list
A double linked list, as the name suggests, is a list with two directions.
Each node has a reference to the next node as well as a reference to the last node.
A doubly linked list can be traversed from front to back as well as from back to front.
Circular linked list
In a circular list, the last node’s successor points to the head node, and the head node’s precursor points to the last node.
The storage mode of the linked list
We know that linked lists are not contiguously allocated in memory. A linked list links nodes in memory through Pointers in the pointer field.
So the list in memory is scattered in memory on a certain address, allocation mechanism depends on the memory management of the operating system.
The definition of a linked list
The definition of a linked list mainly consists of two parts: data field and pointer field.
In Java, since Pointers are excluded, our definition can be data, successor/precursor nodes.
- Singly linked lists:
public class ListNode {
int val;
ListNode next;
ListNode(intx) { val = x; }}Copy the code- Double linked list:
public class ListNode {
int val;
ListNode prev;
ListNode next;
ListNode(intx) { val = x; }}Copy the codeLinked list basic operations
Let’s take a single linked list as an example, and look at some basic operations of a linked list:
- Remove nodes
- Insert the node
The time complexity of both insertion and deletion in the figure is O(1). Note, however, that this is the case where the insertion and deletion of the forward node are already known.
If, the corresponding node also needs to be retrieved, then the time complexity is O(n).
List operation
LeetCode203. Remove linked list elements
☕ Title: 203. Remove linked list elements (leetcode-cn.com/problems/re…)
❓ Difficulty: Easy
📕 Description: if you are given a list with head and an integer val, delete all nodes in the list that satisfy node. val == val and return the new head Node.
💡 ideas:
To delete a linked list node, there are two cases:
- The delete node is the head node: we point the head node to the node next to the head node
- Deleting a node is a non-head node: we need to point the node before the current node to the node next to the current node
Let’s look at the code implementation:
/ * * *@return cn.fighter3.linked_list.ListNode
* @DescriptionRemove list element *@authorThree points *@date2021/7/25 * / at 10:08
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
ListNode cur = head;
ListNode prev = head;
while(cur ! =null) {
ListNode temp = cur.next;
// Delete the node
if (cur.val == val) {
/ / head node
if (cur == head) {
head = temp;
}
// Non-header node
if (cur != head) {
prev.next = cur.next;
}
} else {
prev = cur;
}
cur = temp;
}
return head;
}
Copy the code⏰ Time complexity: O(n).
🏠 Space complexity: O(1).
Now, there’s a slightly more subtle way to do this, which is to use virtual head Pointers — virtual head Pointers are a very useful trick in linked list algorithms.
💡 ideas:
You can set a virtual head pointer with its next pointing to the head node so that the removal of the head node is consistent with that of the normal node.
The code is as follows:
/ * * *@return cn.fighter3.linked_list.ListNode
* @DescriptionRemove list element *@authorThree points *@date2021/7/25 * / at 10:08
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
// Virtual header node
ListNode dummy = new ListNode(-1, head);
ListNode prev = dummy;
ListNode cur = head;
while(cur ! =null) {
if (cur.val == val) {
prev.next = cur.next;
} else {
prev = cur;
}
cur = cur.next;
}
return dummy.next;
}
Copy the code🚗 Time complexity: O(n).
🏠 Space complexity: O(1).
LeetCode707. Design linked lists
☕ Title: 707. Designing linked Lists (leetcode-cn.com/problems/de…)
❓ Difficulty: medium
📕 Description: design the implementation of linked list. You can choose to use single or double linked lists. Nodes in a singly linked list should have two properties: val and next. Val is the value of the current node, and next is a pointer/reference to the next node. If you are using a bidirectional linked list, you also need an attribute, prev, to indicate the last node in the list. Assume that all nodes in the list are 0-index.
Implement these functions in the linked list class:
- Get (index) : Obtains the value of the index node in the linked list. If the index is invalid, -1 is returned.
- AddAtHead (val) : Adds a node with the value val before the first element of the list. After insertion, the new node becomes the first node in the list
- AddAtTail (val) : Appends a node with the value val to the last element of the list.
- AddAtIndex (index,val) : adds a node with the value val before the index node in the list. If index is equal to the length of the list, the node is appended to the end of the list. If the index is greater than the list length, no node will be inserted. If index is less than 0, the node is inserted in the header.
- DeleteAtIndex (index) : If index is valid, delete the index node in the linked list.
Example:
MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); LinkedList. AddAtIndex (1, 2); // Linkedlist.get (1); // Linkedlist.get (1); // Return 2 linkedList.deleteatIndex (1); Linkedlist.get (1); / / return 3Copy the codeTip:
- All val values are within [1, 1000].
- The number of operations will be within [1, 1000].
- Please do not use the built-in LinkedList library.
💡 ideas:
This is a big problem.
A diagram of the basic operations of a linked list has been given earlier.
A more concise approach is to set up a pseudo head node to ensure that the list is never empty, which is much easier to operate.
However, I’ve seen a bit of Java linked list code myself, so I don’t want to take this approach.
The index of the list starts from 0, which causes you to think for 5 minutes and AC for 2 hours.
Ok, let’s go straight to the code:
/ * * *@Author: Three points of evil *@Date: 2021/7/25
* @Description: 707. Design list * https://leetcode-cn.com/problems/design-linked-list/ * <p> * list bound node 0 -- index **/
public class MyLinkedList {
// The number of linked list elements
int size;
/ / head node
ListNode head;
/** * Initialize the list */
public MyLinkedList(a) {
size = 0;
}
/** * Obtain the value of the index node */
public int get(int index) {
// Invalid parameter
if (index < 0 || index >= size) {
return -1;
}
ListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.val;
}
/** * Insert a node */ at the top of the list
public void addAtHead(int val) {
addAtIndex(0, val);
}
/** * Insert a node */ at the end of the list
public void addAtTail(int val) {
addAtIndex(size, val);
}
/** * insert a new node before index; for example, if index is 0, then the new node is the new head of the list. * If index is equal to the length of the list, then the newly inserted node is the last node of the list * if index is greater than the length of the list, then null */ is returned
public void addAtIndex(int index, int val) {
// Invalid parameter
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
// If the list is empty, use it as the head node
if (size == 0) {
head = new ListNode(val);
size++;
return;
}
/ / insert
size++;
ListNode addNode = new ListNode(val);
// Insert before the head node
if (index == 0) {
addNode.next = head;
head = addNode;
return;
}
// Find the precursor node
ListNode pre = head;
for (int i = 0; i < index - 1; i++) {
pre = pre.next;
}
addNode.next = pre.next;
pre.next = addNode;
}
/** * Delete index */
public void deleteAtIndex(int index) {
if (index < 0 || index > size-1) {
return;
}
size--;
/ / head node
if (index == 0) {
head = head.next;
return;
}
// Non-header node
ListNode prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
// Delete the nodeprev.next = prev.next.next; }}Copy the code⏰ Time complexity:
- AddAtHead: O (1)
- AddAtInder, GET, deleteAtIndex: O(n).
- AddAtTail: O (n).
🏠 Space complexity: all operations are O(1).
The virtual header pointer, and the implementation of the double linked list, I’ll leave it blank here.
Double pointer problem solved
Offer 22 is the KTH node in the list
Offer 22. Offer 22. Offer 22.
❓ Difficulty: Easy
📕 Description: Input a linked list and output the KTH node in the list. In order to conform to the habits of most people, this question starts with 1, that is, the last node of the list is the penultimate node.
For example, a linked list has six nodes, starting from the starting node, and their values are 1, 2, 3, 4, 5, 6. The third from the bottom of the list is the node with the value 4.
💡 ideas:
We can do this with a double pointer.
For example, if a pointer pre is in front, it runs 1 step first, and a pointer after is in behind, it runs after. When pre ends, it happens that afer is the second to last.
Code implementation:
/** **@param head
* @param k
* @return* /
public ListNode getKthFromEnd(ListNode head, int k) {
if (head == null) {
return null;
}
ListNode preNode = head, afterNode = head;
int step = 0;
while(preNode! =null) {
preNode = preNode.next;
step++;
if(step > k) { afterNode = afterNode.next; }}return afterNode;
}
Copy the code⏰ Time complexity: O(n).
LeetCode876. The middle node of a linked list
☕ Title: 876. Middle Node of linked List (leetcode-cn.com/problems/mi…)
❓ Difficulty: Easy
📕 Description: given a non-empty single linked list with head, return the middle node of the list.
If there are two intermediate nodes, the second intermediate node is returned.
💡 ideas:
It’s a little bit like the last problem.
The last problem had two Pointers first and then.
This question can be divided into two Pointers fast and slow.
An example of 1 for example, the fast pointer runs two steps, slow pointer runs one step, the fast pointer just runs twice the slow, the fast pointer runs to the end, the slow pointer is not just run to the middle of it!
The code is as follows:
/** * 876@param head
* @return* /
public ListNode middleNode(ListNode head) {
if (head == null) {
return null;
}
// Define the speed pointer
ListNode fastNode = head, slowNode = head;
while(fastNode ! =null&& fastNode.next ! =null) {
// The fast pointer takes two steps
fastNode = fastNode.next.next;
// The slow pointer moves one step
slowNode = slowNode.next;
}
return slowNode;
}
Copy the code⏰ Time complexity: O(n).
Remove the NTH node from the list
☕ topic: 19. Delete the NTH node from the penultimate linked list (leetcode-cn.com/problems/re…)
❓ Difficulty: medium
📕 description: give you a linked list, delete the NTH node from the reciprocal of the list, and return the head node of the list.
** Advanced: ** can you try using a scan implementation?
💡 ideas:
Does this problem start to feel very familiar?
This is the combination of 203. Remove the list element and point to the KTH node in the list.
So the solution, we can also combine these two problems.
- The fast – slow pointer finds the NTH – last node
- The virtual header pointer is deleted
The code is as follows:
/ * * *@return cn.fighter3.linked_list.ListNode
* @DescriptionDelete the NTH node * from the list@authorThree points *@date2021/7/25 ready * /
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return null;
}
// Fast/slow pointer
ListNode fast = head, slow = head;
// Virtual header node
ListNode dummy = new ListNode(-1);
dummy.next = head;
// A pointer starts running from the virtual head node
ListNode preSlow = dummy;
// Count the steps
int step = 0;
while(fast ! =null) {
// Fast takes n steps first
fast = fast.next;
step++;
// Slow start to move
if(step > n) { slow = slow.next; preSlow = preSlow.next; }}// Find the NTH node from the bottom and its precursor
preSlow.next = slow.next;
return dummy.next;
}
Copy the code⏰ Time complexity: O(n).
Offer 52. The first common node in both lists
☕ Title: 876. Middle Node of linked List (leetcode-cn.com/problems/mi…)
❓ Difficulty: Easy
📕 Description: given a non-empty single linked list with head, return the middle node of the list.
If there are two intermediate nodes, the second intermediate node is returned.
💡 ideas:
They say it’s romantic, but I don’t want to hear any romantic bullshit. I just want to make money.
This problem can be solved with double pointer, define two Pointers, when one pointer traverses the list, then turn around to the other list head, continue traversing. They’re going at the same speed so they’re definitely going to meet on the second pass.
As shown (from reference [3]) :
Code implementation:
/** * is the first common node in both lists **@param headA
* @param headB
* @return* /
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
// Define two nodes
ListNode nodeA = headA, nodeB = headB;
while(nodeA ! = nodeB) {// If it doesn't end, it moves back. If it ends, it points to another tree head node
if(nodeA ! =null) {
nodeA = nodeA.next;
} else {
nodeA = headB;
}
// Do the same for the other node
if(nodeB ! =null) {
nodeB = nodeB.next;
} else{ nodeB = headA; }}return nodeA;
}
Copy the code⏰ Time complexity: O(m+n), m and n are lengths of the two lists respectively.
02.07. The intersection of lists and this question are basically the same.
LeetCode206. Reverse the linked list
☕ Title: 206. Reverse Linked List (leetcode-cn.com/problems/re…)
❓ Difficulty: Easy
📕 description: give you the head node of the single linked list, please reverse the list, and return the list after the reversal.
💡 ideas:
This is a very classic problem. How do we do the flip?
Traverse the list, pointing the current node’s successor to the current node.
Here we introduce two additional Pointers:
- a
prevRepresents the forward direction and is used to indicate the direction of the successor when reversing. - a
tempTemp is used to temporarily store the next node. What is temp used for? For traversal, because after the inversion, the original next node already points to Prev.
Seriously, as a C language geek, I was reminded of the days of being dominated by pointer arrays, array Pointers, so I drew a diagram of what it means to be a Java programmer. If anything is wrong, please point it out.
Also found a GIF (reference [1]) :
The code is as follows:
/** * 206@param head
* @return* /
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while(current ! =null) {
// Save the next node
ListNode temp = current.next;
// Modify the subsequent point of the current node
current.next = prev;
// Modify the front-end node
prev = current;
current = temp;
}
return prev;
}
Copy the code⏰ Time complexity: O(n).
LeetCode92. Reverse linked List II
☕ title: 92. Reverse Linked List II (leetcode-cn.com/problems/re…)
❓ Difficulty: medium
📕 Description: You are given the head pointer of a singly linked list with two integers left and right, where left <= right. Invert the list node from position left to position right and return the inverted list.
💡 ideas:
It’s easy to forget to reverse lists, so let’s do a more advanced problem to reinforce that.
So what’s the idea here?
We can split this part of the inverted list, make it a new list, reverse the new list, and reconnect with the nodes before and after.
Code implementation:
/ * * *@return ListNode
* @Description: 92. Reverse linked list II *@authorThree points *@date2021/7/24 0:32 * /
public ListNode reverseBetween(ListNode head, int left, int right) {
// Virtual header node
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = dummy;
// retrieve the front and back nodes of the intercepted sublist
// Move to the node before the left node
int i = 0;
for (; i < left - 1; i++) {
cur = cur.next;
}
// Save the previous node of the left node
ListNode leftPre = cur;
// Move to the right node
for (; i < right; i++) {
cur = cur.next;
}
// Save the next node of the right node
ListNode rightAfter = cur.next;
// 2. Intercept the sub-linked list
// Cut off the right node
cur.next = null;
// The left node is the sublist head node
ListNode sonHead = leftPre.next;
// Cut off the front of the left node
leftPre.next = null;
// 3. Inverse rotor linked list
ListNode rNode = reverseList(sonHead);
// 4: reconnect
leftPre.next = rNode;
sonHead.next = rightAfter;
return dummy.next;
}
/ * * *@return ListNode
* @Description: Reverses the linked list *@authorThree points *@date2021/7/25 10:06 * /
ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while(cur ! =null) {
ListNode temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
Copy the code⏰ Time complexity: O(n).
LeetCode234. Palindromic linked list
☕ title: 234. Palindrome Linked List (leetcode-cn.com/problems/pa…)
❓ Difficulty: Easy
📕 Description: Please determine whether a linked list is a palindrome list.
💡 ideas:
It would be nice to have a bidirectional list, one pointer from the beginning to the end, one pointer from the end to the end, but this is a singly linked list.
So we can use a list to store it, and then we can use a double pointer to go through both ends of the comparison.
The code is as follows:
/** * 234. Palindrome lists * copy values to collections **@param head
* @return* /
public boolean isPalindrome(ListNode head) {
if (head == null) {
return false;
}
List<Integer> nodes = new ArrayList<>(16);
// Put the list values into the collection
while(head ! =null) {
nodes.add(head.val);
head = head.next;
}
// Traversal the collection bidirectionally
int start = 0, end = nodes.size() - 1;
while (start < end) {
if(! nodes.get(start).equals(nodes.get(end))) {return false;
}
start++;
end--;
}
return true;
}
Copy the code⏰ Time complexity: O(n), where n refers to the number of elements in the list,.
🏠 Spatial complexity: O(n), where n refers to the number of elements in the list, since we use an ArrayList to store data.
But there is a further step:
Can you solve this problem with O(n) time and O(1) space?
Since the space complexity is O(1), no new storage structure can be introduced.
Again, if only there were a two-way list, let’s do two-way comparison.
So, think about it, we could flip the second half of the list and compare.
To accomplish this, there are roughly three steps:
- Find the middle node
- Flip the second half of the list
- Compare the first half with the second half
So this is 876. The middle node of the list and 206. Reverse the list.
Code implementation is as follows:
/** * 234@param head
* @return* /
public boolean isPalindrome(ListNode head) {
// Find the intermediate node
ListNode midNode = findMid(head);
// Flip the list
ListNode tailHead = reverseList(midNode);
/ / to compare
while(tailHead ! =null) {
if(head.val ! = tailHead.val) {return false;
}
head = head.next;
tailHead = tailHead.next;
}
return true;
}
/** * Find the intermediate node **@param head
* @return* /
ListNode findMid(ListNode head) {
ListNode fast = head, slow = head;
while(fast ! =null&& fast.next ! =null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
/** * reverse the list **@param head
* @return* /
ListNode reverseList(ListNode head) {
ListNode current = head;
ListNode prev = null;
while(current ! =null) {
// Save the next node
ListNode temp = current.next;
// Modify the subsequent point of the current node
current.next = prev;
// Modify the front-end node
prev = current;
current = temp;
}
return prev;
}
Copy the code⏰ Time complexity: O(n).
🏠 Space complexity: O(1).
LeetCode141. Circular linked list
☕ Title: 141. Circular Linked List (leetcode-cn.com/problems/li…)
❓ Difficulty: Easy
📕 description:
Given a linked list, determine whether there are rings in the list.
If there is a node in the list that can be reached again by continuously tracing the next pointer, there is a loop in the list. To represent the loop in a given list, we use the integer POS to represent where the end of the list is joined into the list (the index starts at 0). If pos is -1, there are no rings in the list. Note: POS is not passed as a parameter, only to identify the actual condition of the linked list.
Returns true if there is a loop in the list. Otherwise, return false.
💡 ideas:
This problem is the classic fast pointer, a pointer running block, a pointer running slow, if the list is a loop, the slow pointer will catch up with the fast pointer.
The code is as follows:
/ * * *@return boolean
* @Description: 141. Ring linked list *@authorThree points *@date2021/7/25 "* /
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
// Define the speed pointer
ListNode fast = head, slow = head;
// Traverse the list
while(fast ! =null&& fast.next ! =null) {
// Move the fast pointer two steps
fast = fast.next.next;
// Move the slow pointer one step
slow = slow.next;
// The fast and slow Pointers meet
if (fast == slow) {
return true; }}return false;
}
Copy the code⏰ Time complexity: O(n).
LeetCode142. Circular Linked List II
☕ Title: 142. Circular Linked List II (leetcode-cn.com/problems/li…)
❓ Difficulty: medium
📕 description:
Given a linked list, return the first node where the list started to enter the loop. Null is returned if the list is loopless.
To represent the loop in a given list, we use the integer POS to represent where the end of the list is joined into the list (the index starts at 0). If pos is -1, there are no rings in the list. Note that pos is only used to identify the ring case and is not passed as an argument to the function.
Note: Modifications to the given list are not allowed.
Advanced:
- Can you use O(1) space to solve this problem?
💡 ideas:
This problem, at first glance, is 141. Circular linked list of advanced, look carefully, not so simple.
141. The ring list fast pointer just catches up with the slow pointer, no matter where it catches up, but this one doesn’t work. We have to return the node we caught up with.
How to do?
We can use a set to store the list nodes in, and if it’s a loop, it’s going to duplicate the nodes.
What do I use for this set? A HashSet is a good idea.
/ * * *@return cn.fighter3.linked_list.ListNode
* @Description: 142. Ring linked list II *@authorThree points *@date2021/7/25 choicest * /
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
HashSet<ListNode> set = new HashSet<>(16);
while(head ! =null) {
// Determine whether the set contains the current element
if (set.contains(head)) {
return head;
}
// Add the element
set.add(head);
// Continue iterating
head = head.next;
}
return null;
}
Copy the code⏰ Time complexity: O(n).
🏠 Space complexity: O(n).
We see that the space complexity O(1) is mentioned in the progression, which involves a very clever double-pointer approach.
The following is a typical deduction [4] :
Code implementation:
/ * * *@return cn.fighter3.linked_list.ListNode
* @Description: 142. Ring linked list II *@authorThree points *@date2021/7/25 20:52 * /
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
// Define fast and slow Pointers
ListNode fast = head, slow = head;
while(fast ! =null&& fast.next ! =null) {
fast = fast.next.next;
slow = slow.next;
// The fast and slow Pointers meet
if (fast == slow) {
// The fast pointer returns to head
fast = head;
while(slow ! = fast) { fast = fast.next; slow = slow.next; }returnfast; }}return null;
}
Copy the code⏰ Time complexity: O(n).
🏠 Space complexity: O(1).
Double linked list problem
LeetCode86. Separate linked lists
☕ Title: 86. Separated List (leetcode-cn.com/problems/pa…)
❓ Difficulty: medium
📕 description:
Given a list with head and a specific value x, separate the list so that all nodes less than x appear before nodes greater than or equal to x.
You should preserve the initial relative position of each node in the two partitions.
💡 ideas:
You can create two lists, one for small nodes, one for large nodes, and finally combine the two lists.
The code is as follows:
/ * * *@return cn.fighter3.linked_list.ListNode
* @Description: 86. Separate the linked list *@authorThree points *@date2021/7/25 21:58 * /
public ListNode partition(ListNode head, int x) {
if (head == null) {
return null;
}
// Define two new linked lists
ListNode small = new ListNode(-1);
ListNode big = new ListNode(-1);
// Small and large list header nodes
ListNode smallHad = small;
ListNode bigHead = big;
ListNode cur = head;
while(cur ! =null) {
if (cur.val < x) {
// Insert node into small linked list
small.next = cur;
small = small.next;
} else {
// Insert nodes into the large linked list
big.next = cur;
big = big.next;
}
cur = cur.next;
}
// Prevent ring formation
big.next = null;
// Merge the list
small.next = bigHead.next;
return smallHad.next;
}
Copy the code⏰ Time complexity: O(n).
LeetCode328. Parity linked list
☕ Title: 328. Parity Linked List (leetcode-cn.com/problems/od…)
❓ Difficulty: medium
📕 description:
Given a single linked list, put all the odd and even nodes together separately. Note that the odd and even nodes here refer to the parity of the node number, not the parity of the node’s value.
Try using the in-place algorithm. Your algorithm should have a space complexity of O(1) and a time complexity of O(Nodes), nodes being the total number of nodes.
Example 1:
Input: 1->2->3->4->5->NULL Output: 1->3->5->2->4->NULLCopy the codeExample 2:
Input: 1 - > 2 - > 3 - > 5 - > 4 - > 7-6 - > > NULL output: 2 - > 3 - > 6-7-1 - > > > 5 - > 4 - > NULLCopy the codeDescription:
- The relative order of odd and even nodes should be maintained.
- The first node of the list is treated as odd, the second as even, and so on.
💡 ideas:
Just like the last problem, we’re going to create two lists, one for odd and one for even digits, and then we’re going to put the two lists together.
The code is as follows:
/ * * *@returnOdd-even linked list *@Description:
* @authorThree points *@date2021/7/25 "* /
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return null;
}
// Lists with odd digits
ListNode odd = new ListNode(-1);
// Lists with even digits
ListNode even = new ListNode(-1);
// Odd and even linked table headers
ListNode oddHead = odd;
ListNode evenHead = even;
// Calculate the position
int index = 1;
/ / traverse
ListNode cur = head;
while(cur ! =null) {
/ /,
if (index % 2= =1) {
odd.next = cur;
odd = odd.next;
} else {
/ / I
even.next = cur;
even = even.next;
}
index++;
cur = cur.next;
}
// Prevent ring formation
even.next = null;
// Merge the list
odd.next = evenHead.next;
return oddHead.next;
}
Copy the code⏰ Time complexity: O(n).
Offer 25. Merge two sorted linked lists
☕ title: Offer 25. Merge two sorted lists (leetcode-cn.com/problems/he…)
❓ Difficulty: Easy
📕 description:
Enter two incrementally sorted lists and merge them so that the nodes in the new list are still incrementally sorted.
Example 1:
Input:1->2->4.1->3->4Output:1->1->2->3->4->4
Copy the code21. leetcode-cn.com/problems/me…
💡 ideas:
Two ascending lists, we need to merge them, so we need to create a new list, traverse the two lists, and put the smaller one behind.
The code is as follows:
/ * * *@return cn.fighter3.linked_list.ListNode
* @DescriptionOffer 25. Merge two sorted lists *@authorThree points *@date2021/7/25 passed * /
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
/ / the new list
ListNode newNode = new ListNode(-1);
// New linked list false header
ListNode newHead = newNode;
while(l1 ! =null&& l2 ! =null) {
// Insert small nodes
if (l1.val <= l2.val) {
newNode.next = l1;
l1 = l1.next;
} else {
newNode.next = l2;
l2 = l2.next;
}
newNode = newNode.next;
}
// Don't miss the last nodenewNode.next = l1 ! =null ? l1 : l2;
return newHead.next;
}
Copy the code⏰ Time complexity: O(n).
Interview question 02.05
☕ Topic: Interview question 02.05. (leetcode-cn.com/problems/su…)
❓ Difficulty: medium
📕 description:
Given two linked list integers, each node contains one digit.
The digits are stored in reverse, so the ones place is at the top of the list.
Write a function that sums the two integers and returns the result as a linked list.
Example:
Input: (7 -> 1 -> 6) + (5 -> 9 -> 2), i.e. 617 + 295 Output: 2 -> 1 -> 9, i.e. 912Copy the code** Advanced: ** Think about it. Suppose these digits are stored in the forward direction. How to solve this problem?
Example:
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5), i.e. 617 + 295 Output: 9 -> 1 -> 2, i.e. 912Copy the code💡 ideas:
These are the four operations that we were familiar with when we were in elementary school.
Two lists are calculated from the beginning, which is the ones place, and the result of the calculation, which needs to be carried, we use a new list to hold the result of the operation.
As shown in figure:
Code implementation is as follows:
/ * * *@return cn.fighter3.linked_list.ListNode
* @Description: Interview question 02.05@authorThree points *@date2021/7/26 2:40 * /
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
/ / the new list
ListNode newNode = new ListNode(-1);
// New list header
ListNode newHead = newNode;
// Used to store the base bits
int carry = 0;
while(l1 ! =null|| l2 ! =null) {
// Check whether the current bit is null. If it is null, set it to 0
int l1Num = l1 == null ? 0 : l1.val;
int l2Num = l2 == null ? 0 : l2.val;
/ / sum
int sum = l1Num + l2Num + carry;
// Update carry
carry = sum / 10;
// Evaluate the node value
int nodeNum = sum % 10;
// Add a node
newNode.next = new ListNode(nodeNum);
// Move the new list pointer
newNode = newNode.next;
// Move two linked list Pointers
if(l1 ! =null) {
l1 = l1.next;
}
if(l2 ! =null) { l2 = l2.next; }}// Finally, according to the carry, determine whether to add nodes in the tail
if(carry ! =0) {
newNode.next = new ListNode(carry);
}
return newHead.next;
}
Copy the code⏰ Time complexity: O(n).
conclusion
In summary, I scribbled a rhyme.
Do simple things repeatedly, do repetitive things seriously, and do serious things creatively!
I am three points of evil, a full stack of civil and military development.
Like, follow don’t get lost, see you next time!
The blogger is an algorithm cute new, brush topic route and train of thought main reference the following big guy! Recommended attention!
Reference:
[1]. Github.com/youngyangya…
[2]. Github.com/chefyuan/al…
[3]. Leetcode-cn.com/problems/li…
[4]. Leetcode-cn.com/problems/li…