sort 将结点存到vector中，利用sort函数进行排序，排序后重新连接各节点即可 C++代码： class Solution { public: ListNode* sortInList(ListNode* head) { vector<ListNode *> a; while (head) { a.push_back(head); head = head->next; } sort(a.begin(), a.end(), cmp); ...

栈 用两个栈分别存两个链表的结点，每次计算两个栈顶结点的相加值，用tmp表示进位，新建一个结点，值为除进位外的值，头插法创建新的结点。 C++代码： class Solution { public: ListNode* addInList(ListNode* head1, ListNode* head2) { ListNode *head = NULL; stack<ListNode *> st1, st2; while (head1) { st1.push(head1); he...

遍历法 首先将两个链表中的结点分别存到两个vector中，看最后一个结点值是否相等，若不相等，则没有公共结点；若相等，则从后往前遍历，直到遇到不相等的结点，此时上一个遍历的结点即为第一个公共结点。 C++代码： class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { if (!pHead1 || !pHead2) {return NULL;} vector<ListNode *> a, b; wh...

C++代码： class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { if (!head) {return NULL;} vector<ListNode *>a; while (head) { a.push_back(head); head = head->next; } if (a.size() == n) {return a[1];} ...

双指针 快指针先走，当走到第K个结点时，慢指针开始走，遍历完后，慢指针指向的结点就是倒数第K个结点。 C++代码： class Solution { public: ListNode* FindKthToTail(ListNode* pHead, int k) { if (!pHead) {return NULL;} ListNode *l = NULL, *r = pHead; int i = 1; while (r->next) { if (i++ == k) {l = pHead;} ...

哈希 遍历链表，用map记录链表中每个结点出现的次数，第一次重复出现的结点就是入口节点。 C++代码： class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { unordered_map<ListNode *, int> mp; while (pHead) { if (mp[pHead]) { return pHead; } mp[pHead]++; ...

双指针法 设置两个指针，一个每次前进两布，一个每次前进一步，若链表有环，则两个指针最后一定会相遇。若快指针走到尽头，两指针仍未相遇，则链表无环。 C++代码： class Solution { public: bool hasCycle(ListNode *head) { ListNode *l = head, *r = head; while (r && r->next) { l = l->next; r = r->next->next; i...

sort函数进行排序 首先用vector存放所有链表指针，然后sort函数进行排序，注意自写比较函数，最后连接vector中的指针即可。 C++代码： class Solution { public: ListNode *mergeKLists(vector<ListNode *> &lists) { if (lists.empty()) { return NULL; } vector<ListNode *> ans; for (int i = 0; i < (...

尾插法 新建前置头指针vhead，尾指针cur并初始化为vhead。若两链表均为遍历完，则把值小的尾插到vhead中。当其中一个链表遍历完后，就把另一个链表链接到vhead后面。 C++代码： class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode *vhead = new ListNode(-1), *cur = vhead; while (pHead1 && pHead2) { if (pHe...

双指针法 和区间翻转解法类似，只需先遍历链表确定长度，然后确定需要几次区间翻转即可。我们需要指针l 和tail分别记录区间翻转后左侧和右侧指针，进行翻转后的善后工作即可。其中，指针l每次赋值为待反转区间前一个指针，tail赋值为待翻转区间第一个指针，反转之后就是最后一个。 C++代码： class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { int len = 0; ListNode *p = head; while (p) { ...

双链表法 区间内反转采用双链表法，与全体翻转不同的是，pre初始应指向区间右侧下一个结点，且翻转完成后，区间左侧前一个结点应指向pre。所以先遍历一遍链表，对指针遍历初始化。最后注意区间边界是开头和结尾的情况即可。 C++代码： class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { ListNode *l, *pre, *p, *t = head; for (int i = 1; i <= n + 1; i++) { ...

双链表法 一前一后两个指针遍历链表实现反转。指针pre初始化为NULL，指针p初始化为pHead。每次操作将p->next指向pre，同时两指针前移，直到p为空，此时pre即为反转后链表的头指针。 ###代码： class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode *pre = NULL, *p = pHead, *t; while (p != NULL) { t = p->next; p->n...