本文总结了单链表的各类经典问题及解法，并进行了分类，代码片段中题目描述注释部分中紧接着题目后面方括号内的数字为该题在 LeetCode 题库中的编号，算法的说明随同附带在代码片段的注释之中，另外不做额外解释。
本文涉及的所有题目及实现代码下载链接为：http://xule.ren/wp-content/uploads/2018/03/LeetCode_list.zip
所有题目默认的单链表结点的定义如下，最后一道题目的结点定义在题目注释中特别指明
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
Removal
链表相较于数组最大的优势便在于给定操作位置后，可在 O(1) 的时间内进行插入或删除操作，只需要调整指针即可，不需要移动元素。LeetCode 上有以下五道与删除操作相关的题目
第 1 题：Delete Node in a Linked List
/**
* 1. Delete Node in a Linked List [237]
*
* Write a function to delete a node (except the tail) in a singly linked list,
* given only access to that node.
* Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node
* with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.
*/
void deleteNode(ListNode *node)
{
ListNode *p = node->next;
node->val = p->val;
node->next = p->next;
delete p;
}
只给定了待删除结点的指针，无法获得指向该结点前驱的指针，直接删除该结点后会导致链表断裂，怎么办？逆向思维，回忆起在二叉搜索树中的删除操作，将前驱或后继的值拷贝给待删除结点后，删除前驱或是后继，这里自然而然地采用后继结点来替代。
第 2 题：Remove Nth Node From End of List
/**
* 2. Remove Nth Node From End of List [19]
*
* Given a linked list, remove the n-th node from the end of list and return its head.
* @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.
* @endexample
* Note:
* Given n will always be valid. Try to do this in one pass.
*/
/**
* The first pointer advances the list by n+1 steps from the beginning, while the
* second pointer starts from the beginning of the list. Now, both pointers are exactly
* separated by n nodes apart. We maintain this constant gap by advancing both pointers
* together until the first pointer arrives past the last node. The second pointer will
* be pointing at the nth node counting from the last. We relink the next pointer of
* the node referenced by the second pointer to point to the node's next next node.
*/
ListNode* removeNthFromEnd(ListNode *head, int n)
{
if (n <= 0)
return head;
ListNode preHead(0);
preHead.next = head;
ListNode *p = &preHead, *q = p;
int i = 0;
for (; p != NULL && i <= n; ++i)
p = p->next;
if (i <= n) // n is greater than the list length
return head;
while (p != NULL)
{
p = p->next;
q = q->next;
}
p = q->next;
q->next = p->next;
delete p;
return preHead.next;
}
第 3 题：Remove Linked List Elements
/**
* 3. Remove Linked List Elements [203]
*
* Remove all elements from a linked list of integers that have value val.
* @example
* Given: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6, val = 6
* Return: 1 -> 2 -> 3 -> 4 -> 5
* @endexample
*/
ListNode* removeElements(ListNode *head, int val)
{
ListNode preHead(0), *p = &preHead;
preHead.next = head;
while (p != NULL)
{
while (p->next != NULL && p->next->val == val)
{
ListNode *q = p->next;
p->next = q->next;
delete q;
}
p = p->next;
}
return preHead.next;
}
注意头结点也可能被删除。凡是涉及到头结点可能会被改动的情况，采用 preHead 技巧能够大幅简化代码的处理，由于 preHead 是局部变量，在函数返回的时候便会被自动析构掉，不用担心内存泄漏的问题。本文后续还会看到大量采用 preHead 技巧来简化处理的题目。
第 4 题：Remove Duplicates from Sorted List
/**
* 4. Remove Duplicates from Sorted List [83]
*
* Given a sorted linked list, delete all duplicates such that each element appear only once.
* @example
* Given 1->1->2, return 1->2.
* @endexample
* @example
* Given 1->1->2->3->3, return 1->2->3.
* @endexample
*/
ListNode* deleteDuplicates(ListNode *head)
{
ListNode *p = head, *q = p != NULL ? p->next : NULL;
while (q != NULL)
{
while (q != NULL && q->val == p->val)
{
q = q->next;
delete p->next;
p->next = q;
}
p = q;
if (p != NULL)
q = p->next;
}
return head;
}
第 5 题：Remove Duplicates from Sorted List II
/**
* 5. Remove Duplicates from Sorted List II [82]
*
* Given a sorted linked list, delete all nodes that have duplicate numbers,
* leaving only distinct numbers from the original list.
* @example
* Given 1->2->3->3->4->4->5, return 1->2->5.
* @endexample
* @example
* Given 1->1->1->2->3, return 2->3.
* @endexample
*/
ListNode* deleteDuplicates(ListNode *head)
{
ListNode preHead(0);
preHead.next = head;
ListNode *r = &preHead, *p = head, *q = p != NULL ? p->next : NULL;
while (q != NULL)
{
bool isDuplicate = false;
while (q != NULL && q->val == p->val)
{
q = q->next;
delete p->next;
p->next = q;
isDuplicate = true;
}
if (isDuplicate)
{
delete p;
r->next = q;
}
else
r = p;
p = q;
if (p != NULL)
q = p->next;
}
return preHead.next;
}
头结点可能被删除，随即想到 preHead 技巧，这种技巧的模板如下
ListNode* func(ListNode *head)
{
/* do something */
ListNode preHead(0);
preHead.next = head;
ListNode *p = &preHead;
/* do something */
return preHead.next;
}
Reorder
由于调整单链表中结点的顺序涉及到大量的指针操作，这类题目备受面试官青睐。LeetCode 上有以下八道与重新排序相关的题目
第 1 题：Reverse Linked List
/**
* 1. Reverse Linked List [206]
*
* Reverse a singly linked list. A linked list can be reversed either
* iteratively or recursively. Could you implement both?
*/
ListNode* reverseList(ListNode *head)
{
ListNode *pPrev = NULL, *pCur = head;
while (pCur != NULL)
{
ListNode *pNext = pCur->next;
pCur->next = pPrev;
pPrev = pCur;
pCur = pNext;
}
return pPrev;
}
ListNode* reverseList(ListNode *head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode *last = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return last;
}
单链表最经典的一道面试题，稍微注意下递归解法中的 last 是在最内层返回的结点，因此是最末的结点，if 语句只会进入一次，head->next = NULL 实际上仅对最外层生效，因为每层的该操作都会被其外面一层重置。
第 2 题：Reverse Linked List II
/**
* 2. Reverse Linked List II [92]
*
* Reverse a linked list from position m to n. Do it in-place and in one-pass.
* @example
* Given 1->2->3->4->5->NULL, m = 2 and n = 4,
* return 1->4->3->2->5->NULL.
* @endexample
* Note:
* Given m, n satisfy the following condition:
* 1 <= m <= n <= length of list.
*/
ListNode* reverseBetween(ListNode *head, int m, int n)
{
if (head == NULL || m == n)
return head;
n -= m;
ListNode preHead(0);
preHead.next = head;
ListNode *p = &preHead, *q = head, *r = q->next;
while (--m > 0)
p = p->next;
q = p->next;
while (n-- > 0)
{
r = q->next;
q->next = r->next;
r->next = p->next;
p->next = r;
}
return preHead.next;
}
第 3 题：Swap Nodes in Pairs
/**
* 3. Swap Nodes in Pairs [24]
*
* Given a linked list, swap every two adjacent nodes and return its head.
* @example
* Given 1->2->3->4, you should return the list as 2->1->4->3.
* @endexample
* Your algorithm should use only constant space. You may not modify the
* values in the list, only nodes itself can be changed.
*/
ListNode* swapPairs(ListNode *head)
{
ListNode preHead(0);
preHead.next = head;
ListNode *p = &preHead, *q = head;
while (q != NULL && q->next != NULL)
{
p->next = q->next;
q->next = q->next->next;
p->next->next = q;
p = q;
q = q->next;
}
return preHead.next;
}
注意套用 preHead 技巧模板就不会有太大问题。
第 4 题：Reverse Nodes in k-Group
/**
* 4. Reverse Nodes in k-Group [25]
*
* 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
*/
ListNode* reverseKGroup(ListNode *head, int k)
{
if (k == 1)
return head;
ListNode preHead(0);
preHead.next = head;
ListNode *p = head, *q = NULL, *r = &preHead;
while (true)
{
int cnt = 0;
for (p = r->next; p != NULL && cnt < k; p = p->next)
++cnt;
if (cnt < k)
break;
p = r->next;
q = p->next;
for (int j = 1; j < k; ++j)
{
p->next = q->next;
q->next = r->next;
r->next = q;
q = p->next;
}
r = p;
}
return preHead.next;
}
同第 2 题是第 1 题的泛化一样，该题是第 3 题的泛化形式，当面试官要求写出特殊情况的代码时，若能给出泛化形式的解法，必然令其印象深刻。
第 5 题：Rotate List
/**
* 5. Rotate List [61]
*
* Given a list, rotate the list to the right by k places, where k is non-negative.
* @example
* Given 1->2->3->4->5->NULL and k = 2,
* return 4->5->1->2->3->NULL.
* @endexample
*/
ListNode* rotateRight(ListNode *head, int k)
{
if (head == NULL || k <= 0)
return head;
int L = 1;
ListNode *t = head;
for (; t->next != NULL; t = t->next)
++L;
k %= L;
if (k == 0)
return head;
ListNode *p = head, *q = p;
for (int i = 0; i < L - k; ++i)
{
q = p;
p = p->next;
}
t->next = head;
q->next = NULL;
return p;
}
数组左旋/右旋是很经典的题目（三次逆序），单链表的旋转解法就大相径庭了，注意左旋 k 次相当于右旋 L – k 次，注意输入参数 k 的处理反映了代码的严谨性，这无论是在面试的过程中还是实际的生产过程中，都极其重要 —— 不要对用户的输入作过多的假设。
第 6 题：Partition List
/**
* 6. Partition List [86]
*
* 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.
* @example
* Given 1->4->3->2->5->2 and x = 3,
* return 1->2->2->4->3->5.
* @endexample
*/
ListNode* partition(ListNode *head, int x)
{
ListNode lo(0), hi(0);
ListNode *p = &lo, *q = &hi;
while (head != NULL)
{
if (head->val < x)
p = p->next = head;
else
q = q->next = head;
head = head->next;
}
p->next = hi.next;
q->next = NULL;
return lo.next;
}
基于枢轴的划分操作是快速排序的核心，在单链表中，交换操作非常麻烦，不如根据值的划分维护两串链表，最后再串起来即可。
第 7 题：Odd Even Linked List
/**
* 7. Odd Even Linked List [328]
*
* Given a singly linked list, group all odd nodes together followed by the even nodes.
* Please note here we are talking about the node number and not the value in the nodes.
* You should try to do it in place.
* The program should run in O(1) space complexity and O(nodes) time complexity.
* @example
* Given 1->2->3->4->5->NULL,
* return 1->3->5->2->4->NULL.
* @endexample
* Note:
* The relative order inside both the even and odd groups should remain as it was in the input.
* The first node is considered odd, the second node even and so on ...
*/
ListNode* oddEvenList(ListNode *head)
{
if (head == NULL)
return NULL;
ListNode *odd = head, *evenhead = head->next, *even = evenhead;
while (even != NULL && even->next != NULL)
{
odd->next = odd->next->next;
even->next = even->next->next;
odd = odd->next;
even = even->next;
}
odd->next = evenhead;
return head;
}
和第 6 题是同样的套路，维护两串链表最后串起来即可。
第 8 题：Insertion Sort List
/**
* 8. Insertion Sort List [147]
*
* Sort a linked list using insertion sort.
*/
ListNode* insertionSortList(ListNode *head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode preHead(0);
preHead.next = head;
ListNode *p = NULL, *q = head; // q is the tail node of ordered sequence
while (q->next != NULL)
{
p = &preHead;
while (p->next != q && p->next->val < q->next->val)
p = p->next;
if (p->next == q && q->val <= q->next->val) // insert to tail means no need to insert
q = q->next;
// 0 -> 3 -> 6 -> 8 -> 1 -> 2 or 0 -> 3 -> 6 -> 8 -> 7 -> 2
// p q r or p q r
else // insert q->next between p and p->next
{
ListNode *r = q->next;
q->next = r->next;
r->next = p->next;
p->next = r;
}
}
return preHead.next;
}
单链表一般都是采用归并排序，当然简单排序也能在其之上实现，只是比较少见些。排序会影响到头结点，记住 preHead 技巧。
Fast-slow Pointers
快慢指针是解决单链表中某类题目的常用技巧，譬如环的检测和找到单链表中位于中间位置的结点。快慢指针的模板如下：
void func(ListNode *head)
{
/* do something */
ListNode *p = head, *q = p;
while (p != NULL && p->next != NULL)
{
p = p->next->next;
q = q->next;
/* do something */
}
/* do something */
}
LeetCode 上有以下四道与快慢指针相关的题目
第 1 题：Sort List
/**
* 1. Sort List [148]
*
* Sort a linked list in O(n log n) time using constant space complexity.
*/
ListNode* sortList(ListNode *head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode *slow = head, *fast = head->next->next;
while (fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
slow = sortList(head);
fast = sortList(fast);
return mergeTwoLists(slow, fast); // see [21]
}
归并排序中需要找到位于单链表中间位置的结点，快慢指针正能扛此重任，代码中的 mergeTwoList() 函数详见后文 Two Lists 大类的第 3 题。
第 2 题：Linked List Cycle
/**
* 2. Linked List Cycle [141]
*
* Given a linked list, determine if it has a cycle in it.
* Follow up:
* Can you solve it without using extra space?
*/
bool hasCycle(ListNode *head)
{
ListNode *p = head, *q = p;
while (p != NULL && p->next != NULL)
{
p = p->next->next;
q = q->next;
if (p == q)
return true;
}
return false;
}
只要单链表中存在环，快慢指针终将会在某次循环中指向同个结点。
第 3 题：Linked List Cycle II
/**
* 3. Linked List Cycle II [142]
*
* 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?
*/
/**
* Using two pointers, one of them one step at a time. another pointer each take two steps.
* Suppose the first meet at step k,the length of the Cycle is r. => 2k - k = nr, k = nr
* Now, the distance between the start node of list and the start node of cycle is s.
* the distance between the start of list and the first meeting node is k (the pointer
* which wake one step at a time waked k steps).the distance between the start node of
* cycle and the first meeting node is m. => s = k - m, s = nr - m = (n-1)r + (r-m),
* here we takes n = 1, hence s = r - m, using one pointer start from the start node of list,
* another pointer start from the first meeting node, all of them wake one step at a time,
* the first time they meeting each other is the start of the cycle.
*/
ListNode* detectCycle(ListNode *head)
{
ListNode *p = head, *q = p;
while (p != NULL && p->next != NULL)
{
p = p->next->next;
q = q->next;
if (p == q)
{
p = head;
while (true)
{
if (p == q)
return p;
p = p->next;
q = q->next;
}
}
}
return NULL;
}
第 4 题：Reorder List
/**
* 4. Reorder List [143]
*
* 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.
* @example
* Given {1,2,3,4}, reorder it to {1,4,2,3}.
* @endexample
*/
void reorderList(ListNode *head)
{
if (head == NULL)
return;
ListNode *p = head, *q = p;
while (p != NULL && p->next != NULL)
{
p = p->next->next;
q = q->next;
}
p = head;
q->next = reverseList(q->next);
ListNode *r = q;
q = q->next;
r->next = NULL;
while (q != NULL)
{
r = q;
q = q->next;
r->next = p->next;
p->next = r;
p = r->next;
}
}
对单链表后半段进行逆序，即可大幅简化处理过程。
Two Lists
此类问题涉及到操作两串单链表（甚至多串单链表）。LeetCode 上有以下五道与两串单链表相关的题目
第 1 题：Add Two Numbers
/**
* 1. Add Two Numbers [2]
*
* You are given two non-empty linked lists representing two non-negative integers.
* The digits are stored in reverse order and each of their nodes contain a single digit.
* Add the two numbers and return it as a linked list.
* You may assume the two numbers do not contain any leading zero,
* except the number 0 itself.
* @example
* Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
* Output: 7 -> 0 -> 8
* Explanation: 342 + 465 = 807.
* @endexample
*/
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
ListNode preHead(0), *p = &preHead;
int extra = 0;
while (l1 != NULL || l2 != NULL || extra > 0)
{
int sum = (l1 != NULL ? l1->val : 0) + (l2 != NULL ? l2->val : 0) + extra;
extra = sum / 10;
p->next = new ListNode(sum % 10);
p = p->next;
l1 = l1 != NULL ? l1->next : l1;
l2 = l2 != NULL ? l2->next : l2;
}
return preHead.next;
}
大数相加的变形，该实现未复用其中一串单链表的既有结点。
第 2 题：Add Two Numbers II
/**
* 2. Add Two Numbers II [445]
*
* You are given two non-empty linked lists representing two non-negative integers.
* The most significant digit comes first and each of their nodes contain a single
* digit. Add the two numbers and return it as a linked list. You may assume the
* two numbers do not contain any leading zero, except the number 0 itself.
* @example
* Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
* Output: 7 -> 8 -> 0 -> 7
* @endexample
* Follow up:
* What if you cannot modify the input lists? In other words, reversing the lists
* is not allowed.
*/
class Solution
{
public:
ListNode* addTwoNumbers(ListNode *l1, ListNode *l2)
{
if (l1 == NULL || l2 == NULL)
return l1 != NULL ? l1 : l2;
int diff = 0, extra = 0;
ListNode *p = l1, *q = l2, *head = NULL;
while (p->next != NULL && q->next != NULL)
{
p = p->next;
q = q->next;
}
bool flag = q->next == NULL;
if (p->next != NULL)
for (; p->next != NULL; p = p->next)
++diff;
else if (q->next != NULL)
for (; q->next != NULL; q = q->next)
++diff;
extra = addTwoNodeVal(flag ? l1 : l2, flag ? l2 : l1, diff);
if (extra == 1)
{
head = new ListNode(1);
head->next = flag ? l1 : l2;
}
else
head = flag ? l1 : l2;
return head;
}
private:
int addTwoNodeVal(ListNode *l1, ListNode *l2, int d)
{
if (l1 == NULL)
return 0;
int sum = l1->val + (d > 0 ? 0 : l2->val) + addTwoNodeVal(l1->next, d > 0 ? l2 : l2->next, d-1);
l1->val = sum % 10;
return sum / 10;
}
};
既然不允许对单链表进行逆序，联想到单链表逆序的递归解法，于是采用递归是最自然的想法，为处理 9999999 + 1 这种不断进位的极端情况，调用递归函数的时候，短的链表在未到和长的链表对齐的时候不执行 ->next 操作，该实现复用了其中偏长的一串单链表的既有结点。
第 3 题：Merge Two Sorted Lists
/**
* 3. Merge Two Sorted Lists [21]
*
* Merge two sorted linked lists and return it as a new list.
* The new list should be made by splicing together the nodes of the first two lists.
* @example
* Input: 1->2->4, 1->3->4
* Output: 1->1->2->3->4->4
* @endexample
*/
ListNode* mergeTwoLists(ListNode *l1, ListNode *l2)
{
ListNode preHead(0);
ListNode *tail = &preHead;
while (l1 != NULL && l2 != NULL)
{
if (l1->val < l2->val)
{
tail->next = l1;
l1 = l1->next;
}
else
{
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 != NULL ? l1 : l2;
return preHead.next;
}
单链表中除逆序外第二经典的题目，归并排序的核心操作，又一个 preHead 技巧简化了代码的例子。
第 4 题：Merge k Sorted Lists
/**
* 4. Merge k Sorted Lists [23]
*
* Merge k sorted linked lists and return it as one sorted list.
* Analyze and describe its complexity.
*/
ListNode* mergeKLists(std::vector<ListNode*>& lists)
{
int i = 0, n = static_cast<int>(lists.size());
if (n == 0)
return NULL;
if (n == 1)
return lists[0];
ListNode preHead(0), *tail = &preHead;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > priorityQ;
for (i = 0; i < n; ++i)
if (lists[i] != NULL)
priorityQ.push(std::pair<int, int>(lists[i]->val, i));
while (!priorityQ.empty())
{
i = priorityQ.top().second;
priorityQ.pop();
tail->next = lists[i];
tail = tail->next;
if (lists[i]->next != NULL)
{
lists[i] = lists[i]->next;
priorityQ.push(std::pair<int, int>(lists[i]->val, i));
}
}
return preHead.next;
}
归并 k 个有序数组的变形，本质相同，都是借助堆来实现 O(n log k) 的时间复杂度，其中 n 是所有单链表结点数目的总和。
第 5 题：Intersection of Two Linked Lists
/**
* 5. Intersection of Two Linked Lists [160]
*
* Write a program to find the node at which the intersection of two singly linked lists begins.
* @example
* The following two linked lists:
* A: a1 → a2
* ↘
* c1 → c2 → c3
* ↗
* B: b1 → b2 → b3
* begin to intersect at node c1.
* @endexample
* Note:
* 1. If the two linked lists have no intersection at all, return null.
* 2. The linked lists must retain their original structure after the function returns.
* 3. You may assume there are no cycles anywhere in the entire linked structure.
* 4. Your code should preferably run in O(n) time and use only O(1) memory.
*/
/**
* We can use two iterations to do that. In the first iteration, we will reset the pointer
* of one linkedlist to the head of another linkedlist after it reaches the tail node.
* In the second iteration, we will move two pointers until they points to the same node.
* Our operations in first iteration will help us counteract the difference. So if two
* linkedlist intersects, the meeting point in second iteration must be the intersection
* point. If the two linked lists have no intersection at all, then the meeting pointer
* in second iteration must be the tail node of both lists, which is null.
*/
ListNode* getIntersectionNode(ListNode *headA, ListNode *headB)
{
if (headA == NULL || headB == NULL)
return NULL;
ListNode *p = headA, *q = headB;
while (p != q)
{
p = p != NULL ? p->next : headB;
q = q != NULL ? q->next : headA;
}
return p;
}
在二叉树最近共同祖先题目中，若存在指向 parent 的指针，则问题便可转化为该题。
Miscellany
LeetCode 上有以下三道与不容易归类的题目
第 1 题：Palindrome Linked List
/**
* 1. Palindrome Linked List [234]
*
* Given a singly linked list, determine if it is a palindrome.
* Follow up:
* Could you do it in O(n) time and O(1) space?
*/
class Solution
{
public:
bool isPalindrome(ListNode *head)
{
s = head;
return check(head);
}
private:
bool check(ListNode *t)
{
if (t == NULL)
return true;
bool palindrome = check(t->next) && s->val == t->val;
s = s->next;
return palindrome;
}
ListNode *s;
};
极其巧妙的实现，当递归进入到最内层的时候，刚好 s 指向头结点，t 指向尾结点，在递归逐层退出的时候，s 指针不断后移，而 t 指针不断前移，最终 s 指向尾结点，t 指向头结点，比较次数为 n 次，n 为单链表长度。
第 2 题：Split Linked List in Parts
/**
* 2. Split Linked List in Parts [725]
*
* Given a (singly) linked list with head node root, write a function to
* split the linked list into k consecutive linked list "parts".
* The length of each part should be as equal as possible: no two parts
* should have a size differing by more than 1. This may lead to some
* parts being null. The parts should be in order of occurrence in the
* input list, and parts occurring earlier should always have a size
* greater than or equal parts occurring later.
* Return a List of ListNode's representing the linked list parts that are formed.
* Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]
* @example
* Input: root = [1, 2, 3], k = 5
* Output: [[1],[2],[3],[],[]]
* Explanation:
* The input and each element of the output are ListNodes, not arrays.
* For example, the input root has root.val = 1, root.next.val = 2,
* root.next.next.val = 3, and root.next.next.next = null.
* The first element output[0] has output[0].val = 1, output[0].next = null.
* The last element output[4] is null, but it's string representation as a ListNode is [].
* @endexample
* @example
* Input:
* root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
* Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
* Explanation:
* The input has been split into consecutive parts with size difference at most 1,
* and earlier parts are a larger size than the later parts.
* @endexample
* Note:
* 1. The length of root will be in the range [0, 1000].
* 2. Each value of a node in the input will be an integer in the range [0, 999].
* 3. k will be an integer in the range [1, 50].
*/
std::vector<ListNode*> splitListToParts(ListNode *root, int k)
{
int L = 0;
for (ListNode *p = root; p != NULL; p = p->next)
++L;
int _n = L / k, _k = L % k;
std::vector<ListNode*> res(k, NULL);
ListNode *p = root, *q = NULL;
for (int j = 0; p != NULL && j < k; ++j)
{
int n = j < _k ? _n + 1 : _n;
res[j] = p;
for (int i = 1; i < n; ++i)
p = p->next;
q = p->next;
p->next = NULL;
p = q;
}
return res;
}
先遍历一遍以求出链表长度，随后问题就简单了。
第 3 题：Copy List with Random Pointer
/**
* 3. Copy List with Random Pointer [138]
*
* A linked list is given such that each node contains an additional
* random pointer which could point to any node in the list or null.
* Return a deep copy of the list.
*/
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
RandomListNode* copyRandomList(RandomListNode *head)
{
RandomListNode *p = head, *q = NULL;
while (p != NULL)
{
q = new RandomListNode(p->label);
q->next = p->next;
p->next = q;
p = q->next;
}
p = head;
while (p != NULL)
{
q = p->next;
q->random = p->random != NULL ? p->random->next : NULL;
p = q->next;
}
p = head;
RandomListNode *dupHead = head != NULL ? head->next : NULL;
while (p != NULL)
{
q = p->next;
p->next = q->next;
p = p->next;
q->next = p != NULL ? p->next : NULL;
}
return dupHead;
}
一道风格迥异的题目，该题在《剑指 Offer》一书中有收录，解法不太容易想到。在原链表每个结点之后复制一个一模一样的结点（这是能够正确设置 random 指针的唯一方法），最后再将两串黏连的链表分割开来。