24. Swap nodes in a linked table two by two
You are given a chained table, and two by two, you exchange the neighboring nodes in it and return the head node of the exchanged chained table. You must complete this problem without modifying the values inside the nodes (i.e., only node swaps can be performed).
Example 1:
Input: head = [1,2,3,4]
Output: [2,1,4,3]
Example 2:
Input: head = []
Output: []
Example 3:
Input: head = [1]
Output: [1]
Tip:
The number of nodes in the chain table is in the range [0, 100].
0 <= <= 100
Positive solution (analog)
The whole exchange process:
Upcode (●'◡'●)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0); // Setting up a virtual head node
dummyHead->next = head; // Point the virtual head node to thehead，This makes it easier to do deletions later on
ListNode* cur = dummyHead;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* pre = cur->next; // Record temporary nodes
ListNode* nex = cur->next->next->next; // Record temporary nodes
cur->next = cur->next->next; // step one
cur->next->next = pre; // step Two
cur->next->next->next = nex; // step Three
cur = cur->next->next; // curMobile Two，Prepare for the next round of exchanges
}
ListNode* result = dummyHead->next;
delete dummyHead;
return result;
}
};
19. Delete the penultimate N node of the chain table
Given a linked list, delete the nth node from the bottom of the list and return the head node of the list.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
Tip:
The number of nodes in the linked table is sz
1 <= sz <= 30
0 <= <= 100
1 <= n <= sz
Advanced: can you try to implement it using a trip scan?
The power button gives a one-way chained table, so you can only find it from front to back;
However, the question asks to delete the penultimate N elements, so you have to find another way;
Positive solution (double pointer)
Define f,s, two pointers, the f pointer goes N steps first, then f,s, move together until f moves to the end of the chain table;
At this point, s points to the penultimate Nth element;
The idea is simple to write. It's also simple 😃
Upcode (●'◡'●)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* s = dummyHead;
ListNode* f = dummyHead;
while(n-- && f != NULL) {
f = f->next;
}
f = f->next;
while (f != NULL) {
f = f->next;
s = s->next;
}
s->next = s->next->next;
return dummyHead->next;
}
};
This accomplishes what the title calls for with one scan.
Interview Question 02.07. Intersecting Chained Tables
Given the head nodes headA and headB of two single linked tables, find and return the starting node where the two single linked tables intersect. If there is no intersection, return null.
The diagram shows two linked lists intersecting starting at node c1:
The title data guarantees that there are no rings in the entire chain structure.
Note that after the function returns its result, the chain table must retain its original structure.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The value of the intersected node is 8 (note that it cannot be 0 if two linked tables intersect).
Counting from their respective headers, chain table A is [4,1,8,4,5] and chain table B is [5,0,1,8,4,5].
In A, there are 2 nodes before the intersection node; in B, there are 3 nodes before the intersection node.
Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The value of the intersected node is 2 (note that it cannot be 0 if two linked tables intersect).
Counting from their respective headers, chain table A is [0,9,1,2,4] and chain table B is [3,2,4].
In A, there are 3 nodes before the intersecting node; in B, there is 1 node before the intersecting node.
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Explanation: Starting from their respective headers, list A is [2,6,4] and list B is [1,5].
Since the two tables do not intersect, intersectVal must be 0, and skipA and skipB can be any values.
The two lists do not intersect, so null is returned.
Tip:
The number of nodes in listA is m
The number of nodes in listB is n
0 <= m, n <= 3 * 104
1 <= <= 105
0 <= skipA <= m
0 <= skipB <= n
If listA and listB have no intersection, intersectVal is 0.
If listA and listB have intersection, intersectVal == listA[skipA + 1] == listB[skipB + 1]
Advanced: can you design a solution with O(n) time complexity and only O(1) memory?
Note: Just because the values of the nodes are equal does not mean they are the same node.
That's why the point of intersection in example 1 is not 1 but 8;
Positive solution (double pointer)
Define two pointers cur1,cur2,traverse A and B to find the length;
Let cur1 point to the longer one, and then remove the number of nodes in cur1 from the beginning until it is equal to cur2;
At this point, traverse cur1 and cur2 simultaneously when the\(cur1_i==cur2_i\)When you return the\(cur1_i\)
Upcode (●'◡'●)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0, lenB = 0;
while (curA != NULL) {
lenA++;
curA = curA->next;
}
while (curB != NULL) {
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
if (lenB > lenA) {
swap (lenA, lenB);
swap (curA, curB);
}
int gap = lenA - lenB;
while (gap--) {
curA = curA->next;
}
while (curA != NULL) {
if (curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};
This fulfills the title requirement:
-Time Complexity\(O(n)\)
-Space complexity\(O(1)\)
It's not easy to write a blog, so please give me some support 8~!