Directory
1 Invert the specified interval
1.1 Plug-in method
1.2 Threading the needle
2 Exchange the nodes in the linked list two by two
3 Singly linked list plus 1
4 List addition
4.1 Implementation using a stack
4.2 Implementation using linked list inversion
5 Revisiting the problem of palindrome sequence of linked list
1 Specifies interval inversion
LeetCode92: Give you the head pointer head of the singly 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.
Example 1: Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5]
1.1 plug method
The overall idea of reversal is that in the interval that needs to be reversed, every time a node is traversed, let this new node come to the starting position of the reversed part.
public static ListNode reverseBetween2(ListNode head, int left, int right) {
ListNode dummyNode = new ListNode(-1);
dummyNode. next = head;
ListNode pre = dummyNode;
for (int i = 0; i < left - 1; i ++ ) {
pre = pre. next;
}
ListNode cur = pre.next;
ListNode next;
for (int i = 0; i < right - left; i ++ ) {
next = cur. next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummyNode. next;
}
1.2 Threading the needle
First determine the part that needs to be reversed, that is, between left and right in the figure below, and then splice the three linked lists together. This method is similar to a tailor, find the correct position, cut it down, and then sew it back. In this way, the problem becomes how to mark the four positions in the figure below, and how to reverse the linked list between left and right.
- Step 1: First reverse the area to be reversed;
- Step 2: Point the next pointer of pre to the head node of the reversed linked list, and point the next pointer of the tail node of the reversed linked list to succ.
public static ListNode reverseBetween(ListNode head, int left, int right) {
// Because the head node may change, using a virtual head node can avoid complicated classification discussions
ListNode dummyNode = new ListNode(-1);
dummyNode. next = head;
ListNode pre = dummyNode;
// 1. Go to the node before left
for (int i = 0; i < left - 1; i ++ ) {
pre = pre. next;
}
// 2. Then go to the right node
ListNode rightNode = pre;
for (int i = 0; i < right - left + 1; i ++ ) {
rightNode = rightNode. next;
}
// 3. Cut out the linked list to be reversed
ListNode leftNode = pre.next;
ListNode succ = rightNode. next;
rightNode. next = null;
// 4. Reverse the linked list
reverseList(leftNode);
// 5. Retrieve the original linked list
pre.next = rightNode;
leftNode. next = succ;
return dummyNode. next;
}
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
2 Exchange the nodes in the linked list in pairs
LeetCode24. Give you a linked list, exchange the adjacent nodes in it two by two, and return the head node of the exchanged linked list. You must complete this exercise without modifying the values inside the nodes (i.e. only node swaps).
If the original order is dummy -> node1 -> node2, the relationship between the two nodes after the exchange will become dummy -> node2 -> node1.
public static ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(-1);
dummyHead. next = head;
ListNode temp = dummyHead;
while (temp. next != null & amp; & amp; temp. next. next != null) {
ListNode node1 = temp. next;
ListNode node2 = temp.next.next;
temp.next = node2;
node1.next = node2.next;
node2.next = node1;
temp = node1;
}
return dummyHead. next;
}
3 singly linked list plus 1
LeetCode369. Use a non-empty singly linked list to represent a non-negative integer, and then add one to the integer. You can assume that the integer doesn’t have any leading 0’s other than 0 itself. Each digit of this integer is arranged in the order that the high bit is at the head of the linked list and the low bit is at the end of the linked list.
Example: Input: [1,2,3] Output: [1,2,4]
The calculation starts from the low bit, and the linked list starts from the high bit, so it must be reversed to process. At this time, the stack can be used, or the linked list can be reversed to achieve.
The idea based on the implementation of the stack is not complicated. First, put the linked list traversal given in the title into the stack, and then pop the top number digit from the stack. When adding, consider the carry situation and it will be ok. After adding, according to whether If it is greater than 0, it will be regarded as the next carry.
public static ListNode plusOne(ListNode head) {
Stack<Integer> st = new Stack();
while (head != null) {
st.push(head.val);
head = head. next;
}
ListNode dummy = new ListNode(0);
int carry = 0;
int adder = 1;
while (!st.empty() || carry > 0) {
int digit = st.empty() ? 0 : st.pop();
int sum = digit + adder + carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
ListNode cur = new ListNode(sum);
cur.next = dummy.next;
dummy.next = cur;
adder = 0;
}
return dummy. next;
}
If you don’t use a stack here, what should you do if you use a linked list inversion to achieve it?
public static ListNode plusOneByReverse(ListNode head) {
ListNode revList = reverseListAll(head);
ListNode curr = revList;
int carry = 0;
int adder = 1;
while (curr != null) {
int sum = curr.val + adder + carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
curr.val = sum;
adder = 0;
curr = curr. next;
}
ListNode resList = reverseListAll(revList);
if (carry > 0) {
ListNode carryNode = new ListNode(carry);
carryNode. next = resList;
return carryNode;
} else {
return resList;
}
}
public static ListNode reverseListAll(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
4 linked list addition
LeetCode445 question, you are given two non-empty linked lists to represent two non-negative integers. The highest digit of the number is at the beginning of the linked list. Each of their nodes stores only a single digit. Adding these numbers returns a new linked list. You can assume that neither number starts with a zero other than the number 0.
4.1 Implementation using stack
First push the elements of the two linked lists to the stack separately, and then pop them out together, and calculate the two results separately. Then take the modulus of the calculation result, save the modulus in a new linked list, and save the carry to the next round. When you’re done, do another inversion.
We know that there are two types of insertion in the linked list: head insertion and tail insertion. The head insertion method is to insert a new node before the head every time. The tail insertion method is to insert all new nodes into the end of the linked list. The difference between the two is that the order of the tail insertion method is consistent with the original linked list, while the head insertion method is in the reverse order of the original linked list, so if you don’t want to reverse the last step above, you can insert the new node with the head insertion method.
public static ListNode addInListByStack(ListNode head1, ListNode head2) {
Stack<ListNode> st1 = new Stack<ListNode>();
Stack<ListNode> st2 = new Stack<ListNode>();
while (head1 != null) {
st1. push(head1);
head1 = head1. next;
}
while (head2 != null) {
st2.push(head2);
head2 = head2. next;
}
ListNode newHead = new ListNode(-1);
// carry
int carry = 0;
while (!st1.empty() || !st2.empty() || carry != 0) {
ListNode a = new ListNode(0);
ListNode b = new ListNode(0);
if (!st1. empty()) {
a = st1. pop();
}
if (!st2. empty()) {
b = st2. pop();
}
int sum = a.val + b.val + carry;
// handle carry
carry = sum / 10;
// process the result using head interpolation
ListNode curr = new ListNode(sum % 10);
curr.next = newHead.next;
newHead.next = curr;
}
return newHead. next;
}
4.2 Implementation using linked list reversal
If you use linked list inversion, first invert the two linked lists, and then invert the result after the final calculation. There are three inversion operations in total, so it is better to extract one method of inversion.
public static ListNode addInListByReverse(ListNode head1, ListNode head2) {
head1 = reverse(head1);
head2 = reverse(head2);
ListNode head = new ListNode(-1);
ListNode curr = head;
int carry = 0;
while (head1 != null || head2 != null) {
int sum = carry;
if (head1 != null) {
sum + = head1.val;
head1 = head1. next;
}
if (head2 != null) {
sum + = head2.val;
head2 = head2. next;
}
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr. next;
}
if (carry != 0) {
curr.next = new ListNode(carry);
}
return reverse(head. next);
}
private static ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
5 Re-discuss the problem of palindrome sequence of linked list
“Fast and slow pointer + half reversal” method
public boolean isPalindrome(ListNode head) {
if(head == null || head. next == null) {
return true;
}
ListNode slow = head, fast = head;
ListNode pre = head, prepre = null;
while(fast != null & amp; & amp; fast. next != null) {
pre = slow;
slow = slow. next;
fast = fast.next.next;
//Reverse the first half of the linked list
pre.next = prepre;
prepre = pre;
}
if(fast != null) {
slow = slow. next;
}
while(pre != null & amp; & amp; slow != null) {
if(pre.val != slow.val) {
return false;
}
pre = pre. next;
slow = slow. next;
}
return true;
}