输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。示例1:输入:1->2->4, 1->3->4输出:1->1->2->3->4->4思路:递归。简记函数签名为f(x,y)=z,其中x,y为待合并的两条链表,z为合并后的链表头节点。比较两条链表的头节点,较小节点为合并后的头节点newHead,把newHead的next指向下一条合并后的头节点。即有如下公式:f(x,y)->next = f(x->next,y) (x < y) f(x,y)->next = f(x,y->next) (x > y)考虑基础情况:如果x为nullptr,则返回y,否则再判断y是否为nullptr,如果为nullptr则返回x代码:/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x),

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。思路1:直观思路,定义两个指针,一个指向当前节点,一个指向前一个节点,每次把当前节点的next指向前一个节点,然后当前指针指向变换前的next,前一个指针指向当前指针。重复这个过程,直到当前指针指向nullptr代码:/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* cur = head; ListNode* pre = nullptr; while(cur) { ListNode* next = cur->next;

给定一个链表,返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环,则返回 null。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。说明:不允许修改给定的链表。思路:两个指针,一快一慢,快指针一次走两步,慢指针一次走一步,如果有环,则两指针必会相遇。假设链表的头为head,入口点为enter,相遇点为meet。head到enter的距离为a,enter到meet的距离为b,meet到enter的距离为c。两指针相遇时,快指针走过的距离是慢指针的两倍,假设此时快指针绕了m圈,慢指针绕了n圈。则有等式a+b+m(b+c)=2(a+b+n(b+c)),由此等式可推出 m(b+c)=a+b+2n(b+c) >> (m-2n)(b+c)=a+b >> (m-2n)(b+c)-(b+c)+c = a >> (m-2n-1)(

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。示例:给定一个链表: 1->2->3->4->5, 和 k = 2.返回链表 4->5.思路:两个指针,一前一后,前面的指针先走k步,然后后面的指针跟进一起走,当前面的指针为nullptr时,后面的指针就是答案。代码:/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* getKthFromEnd(ListNode* head, int k) { if(head

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。思路:两个指针:left、right。left指向下标0,right指向下标数组长度减一。如果left指向的数为奇数,则left++,否则停下,如果right指向的数为偶数,则right--,否则停下。然后交换left和right指向的数。重复这个过程。代码:class Solution { public: vector<int> exchange(vector<int>& nums) { int len = nums.size(); int right = len-1; int left = 0; while(left < right) { while(left < len && nums[left]&1) { left++; } w