鏈表題目是有套路的年堆，如下4個(gè)方法：
- 鏈表逆序 (n個(gè)節(jié)點(diǎn)進(jìn)行逆序丹墨，實(shí)際上循環(huán)進(jìn)行n-1次)
- 2個(gè)指針 (拆分恼除、拼接疾牲、合并植捎、求中點(diǎn))
- 鏈表成環(huán)
- 使用額外空間保存
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
該題目幾乎使用到了所有的套路
1. 使用2個(gè)指針，求出鏈表中點(diǎn)
2. 將后半段鏈表逆序
3. 使用3個(gè)指針阳柔，將2兩個(gè)鏈表拼接起來(lái)
void reorderList(ListNode* head) {
ListNode preHead1 = ListNode(INT_MIN);
preHead1.next = head;
ListNode *preMid = &preHead1, *mid = head;
while (head && head->next) {
preMid = mid;
mid = mid -> next;
head = head -> next -> next;
}
preMid -> next = NULL;
ListNode preHead2 = ListNode(INT_MIN);
preHead2.next = mid;
ListNode *pre = &preHead2, *cur = pre->next, *nex = NULL;
while (cur && (nex = cur->next)) {
cur->next = nex->next;
nex->next = pre->next;
pre->next = nex;
}
ListNode *left = preHead1.next, *right = preHead2.next, *pt = &preHead1;
while (left && right) {
pt->next = left;
left = left->next;
pt = pt->next;
pt->next = right;
right = right->next;
pt = pt->next;
}
head = preHead1.next;
}
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
對(duì)鏈表中一段區(qū)域進(jìn)行逆序焰枢。思路很清楚：找出該段的的前一個(gè)節(jié)點(diǎn)，對(duì)該段長(zhǎng)度的節(jié)點(diǎn)進(jìn)行逆序舌剂，并將pre節(jié)點(diǎn)和后面的連接起來(lái)济锄。
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode preHead = ListNode(INT_MIN);
preHead.next = head;
ListNode *pre = &preHead;
for (int i = 1; i <= m - 1; ++i)
pre = pre -> next;
ListNode *cur = pre->next, *nex = cur->next;
for (int i = 0; i < n - m; ++i) {
cur->next = nex->next;
nex->next = pre->next;
pre->next = nex;
nex = cur->next;
}
return preHead.next;
}
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
每k個(gè)節(jié)點(diǎn)為一組，內(nèi)部逆序
求出鏈表長(zhǎng)度霍转，當(dāng)鏈表長(zhǎng)度 >= k時(shí)才進(jìn)行循環(huán)荐绝，每k個(gè)節(jié)點(diǎn)進(jìn)行逆序并和之前拼接
left記錄上組最后一個(gè)，pt記錄本組第一個(gè)避消，right記錄本組的遍歷
ListNode* reverseKGroup(ListNode* head, int k) {
if(head==NULL||k==1) return head;
ListNode preHead = ListNode(INT_MIN);
preHead.next = head;
int count=0;
ListNode *pre = &preHead, *cur = &preHead, *nex = NULL;
while(cur = cur->next)
count++;
while(count>=k) {
cur = pre->next;
nex = cur->next;
for(int i=1;i<k;++i) {
cur->next=nex->next;
nex->next=pre->next;
pre->next=nex;
nex=cur->next;
}
pre = cur;
count -= k;
}
return preHead.next;
}
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
經(jīng)典的求鏈表是否有環(huán)的問(wèn)題低滩，使用快慢指針解決，如果會(huì)相遇則有環(huán)岩喷。
bool hasCycle(ListNode *head) {
if (!head) return false;
ListNode *slow = head, *fast = head;
while (slow && fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
如果不考慮空間復(fù)雜度恕沫，可以使用set保存已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。
空間復(fù)雜度為O(1)的方法是均驶，快慢指針相遇的地方離入口的距離和從頭出發(fā)的距離是一樣的昏兆。具體原因
ListNode *detectCycle(ListNode *head) {
if (!head) return NULL;
ListNode *slow = head, *fast = head, *entry = head;
while (slow && fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
while (entry != slow) {
slow = slow->next;
entry = entry->next;
}
return entry;
}
}
return NULL;
}
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
去除倒數(shù)第k個(gè)節(jié)點(diǎn)。使用2個(gè)指針妇穴，指針的距離為k+1爬虱。
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode preHead = ListNode(INT_MIN);
preHead.next = head;
ListNode *left = &preHead, *right = head;
int count = 0;
while (right) {
if (count >= n) left = left->next;
right = right->next;
++count;
}
if (left->next) left->next = left->next->next;
return preHead.next;
}
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
有序鏈表去重。使用2個(gè)指針腾它，當(dāng)right的指針指向的值大于left指針指向的值跑筝，則left指針的下一個(gè)指向該right指針指向的節(jié)點(diǎn)，并移動(dòng)left指針瞒滴。
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return head;
ListNode preHead = ListNode(INT_MIN);
preHead.next = head;
ListNode *left = head, *right = head;
while (right) {
if (right->val > left->val) {
left->next = right;
left = left->next;
}
right = right->next;
}
left->next = NULL;
return preHead.next;
}
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
1. left負(fù)責(zé)加入不重復(fù)節(jié)點(diǎn)曲梗，right負(fù)責(zé)遍歷數(shù)組
2. right每次遇到新元素便遍歷到該值的最后一個(gè)節(jié)點(diǎn)
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return head;
ListNode preHead = ListNode(INT_MIN);
preHead.next = head;
ListNode *left = &preHead, *right = head;
while (right) {
bool duplicated = false;
while (right && right->next && right->val == right->next->val) {
right = right->next;
duplicated = true;
}
if (!duplicated) {
left->next = right;
left = left->next;
}
right = right->next;
}
left->next = NULL;
return preHead.next;
}
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
將鏈表拆分成2部分，最后連接起來(lái)
1. 新建兩個(gè)dump節(jié)點(diǎn)leftHead妓忍、rightHead
2. left注暗、right兩個(gè)指針負(fù)責(zé)為兩個(gè)新鏈表添加節(jié)點(diǎn)
3. head負(fù)責(zé)遍歷原始鏈表
ListNode* partition(ListNode* head, int x) {
ListNode leftHead = ListNode(INT_MIN);
ListNode rightHead = ListNode(INT_MIN);
ListNode *left = &leftHead, *right = &rightHead;
while (head) {
if (head->val < x) {
left->next = head;
left = left->next;
} else {
right->next = head;
right = right->next;
}
head = head->next;
}
left->next = rightHead.next;
right->next = NULL;
return leftHead.next;
}
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
這道題目可以使用在每個(gè)鏈表中當(dāng)前節(jié)點(diǎn)中選取val最小的嘉冒，然后拼接起來(lái)。或者遞歸地兩兩合并举户，利用分治的思想蓬豁。時(shí)間復(fù)雜度分別是O(kn)、O(nlogk)。然而實(shí)際使用分治的方法要快很多琼蚯。
ListNode *mergeTwoLists(ListNode* l1, ListNode* l2) {
if (NULL == l1) return l2;
else if (NULL == l2) return l1;
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
if (lists.empty()) return NULL;
int len = lists.size();
while (len > 1) {
for (int i = 0; i < len / 2; ++i) {
lists[i] = mergeTwoLists(lists[i], lists[len - 1 - i]);
}
len = (len + 1) / 2;
}
return lists.front();
}
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
1. 遍歷鏈表，求出鏈表長(zhǎng)度惠况，并將鏈表首尾相連
2. 遍歷到len - (k%len)的位置遭庶，將鏈表斷開(kāi)
ListNode* rotateRight(ListNode* head, int k) {
if (!head) return head;
int len = 1;
ListNode *newH = head, *tail = head;
while (tail -> next) {
len++;
tail = tail -> next;
}
tail -> next = head;
if (k %= len) {
for (int i = 0; i < len - k; ++i) tail = tail->next;
}
newH = tail->next;
tail->next = NULL;
return newH;
}
