基础算法解决相对应问题思路（一）
1. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
解题思路：快慢指针，先让快指针走k步，快慢指针一起走，直到快速指针走完，返回慢指针
Kotlin:
/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
* var next: ListNode? = null
* }
*/
class Solution {
fun getKthFromEnd(head: ListNode?, k: Int): ListNode? {
var slow = head
var fast = head
for(i in 0..k-1){
fast = fast?.next
}
while(fast != null) {
fast = fast?.next
slow = slow?.next
}
return slow
}
}
/**
* 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) {
ListNode * slow = head;
ListNode * fast = head;
int i;
for(i=0;i<k;++i){
fast = fast->next;
}
while(fast!= NULL) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode slow = head;
ListNode fast = head;
for(int i=0;i<k;++i){
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
2. (快慢指针) 给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
解题思路：两个指针，快慢指针。判断奇数个列表和偶数个列表。快指针移动两步next.next, 慢指针一步一步
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast !=null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
3. 编写一个程序，找到两个单链表相交的起始节点。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
解题思路：最优解
分别为链表A和链表B设置指针A和指针B，然后开始遍历链表，如果遍历完当前链表，则将指针指向另外一个链表的头部继续遍历，直至两个指针相遇。
最终两个指针分别走过的路径为：
指针A :a+c+b
指针B :b+c+a
明显 a+c+b = b+c+a,因而如果两个链表相交，则指针A和指针B必定在相交结点相遇。
image.png
Kotlin:
/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
* var next: ListNode? = null
* }
*/
class Solution {
fun getIntersectionNode(headA:ListNode?, headB:ListNode?):ListNode? {
if(headA == null || headB == null) return null
var a:ListNode? = headA
var b:ListNode? = headB
while(a != b){
if(a != null) {
a = a.next
}else {
a = headB
}
if(b != null) {
b = b.next
} else {
b = headA
}
}
return a
}
}
Java:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode pA = headA;
ListNode pB = headB;
while(pA != pB) {
if(pA != null)
pA = pA.next;
else
pA = headB;
if(pB!=null)
pB = pB.next;
else
pB = headA;
}
return pA;
}
}
C++:
/**
* 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) {
if(!headA || !headB) return NULL;
ListNode *a = headA;
ListNode *b = headB;
while(headA != headB){
if(headA) {
headA = headA->next;
}else {
headA = b;
}
if(headB) {
headB = headB->next;
}else {
headB = a;
}
}
return headA;
}
};
不建议思路
1. 暴力法
对链表A中的每一个结点 a_ia
遍历整个链表 B 并检查链表 B 中是否存在结点和 a_ia
相同。
复杂度分析
时间复杂度 : (mn)(mn)。
空间复杂度 : O(1)O(1)。
2. 哈希表法
遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表 B 中的每一个结点 b_ib
是否在哈希表中。若在，则 b_ib 为相交结点。
复杂度分析
时间复杂度 : O(m+n)O(m+n)。
空间复杂度 : O(m)O(m) 或 O(n)O(n)。
4. 获取链表的长度
public int getLength(Node head) {
if (head == null) {
return 0;
}
int length = 0;
Node current = head;
while (current != null) {
length++;
current = current.next;
}
return length;
}
5. 翻转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：0 <= 节点个数 <= 5000
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while(cur != null) {
ListNode nextNode = cur.next;
cur.next = prev;
prev = cur;
cur = nextNode;
}
return prev;
}
}
延伸-递归方式翻转链表
public ListNode reverseList(ListNode head, ListNode prev) {
if (head.next == null) {
head.next = prev;
return head;
} else {
ListNode node = reverseList(head.next, head);
head.next = prev;
return node;
}
}
6. 查找任一重复元素：排序法，哈希法，原地置换法
三种方法
方法一：直接排序，然后遍历，思路很简单但是执行起来比较麻烦
方法二：哈希表，就是找另一个数组，把nums的元素一个一个放进去，放进去之前判断里面有没有，如果里面已经有了那就遇到重复元素，结束。贼麻烦！时间复杂度O(N2),空间O(N)
方法三：原地置换。（0将数组对应为哈希表）如果数组中不存在重复元素，那么应该下标与数字对应（长度为n的数组，其中数字的范围都在0到n-1范围内）。如果遇到下标i与nums[i]不一样，那么就要把这个nums[i]换到它应该去的下标下面。如果那么下标下面已经被占了，那么就找到了重复，结束就好了！
0～n-1中缺失的数字
暴力查找或者二分查找
剑指 Offer 21 调整数组顺序使奇数位于偶数前面
[1,2,3,4]--->[1,3,2,4]
思路一：
额外存储，新建一个一摸一样的空数组。循环一次判断，奇数存放在前面，偶数倒着存放
思路二：
C++ vector sort
class Solution {
private:
static bool cmp(int a, int b) {
return a % 2 == b % 2 ? a < b : a % 2 == 1;
}
public:
vector<int> exchange(vector<int>& nums) {
sort(nums.begin(), nums.end(), cmp);
return nums;
}
};
思路三：头尾双指针
判断都是偶数，尾部指针前移。否则交换
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int n=nums.size();
int l=0,r=n-1;
while(l<r)
{
if(nums[l]%2==0&&nums[r]%2==0) //两边均为偶数
r--;
else if(nums[l]%2==0&&nums[r]%2!=0) //左边为偶数，右边为奇数
{
swap(nums[l],nums[r]);
l++,r--;
}
else //左边为奇数
l++;
}
return nums;
}
};
7. 删除排序数组中的重复项 II
要求：
给定一个增序排列数组 nums ，你需要在 原地 删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
写法一，普通写法
class Solution {
public int removeDuplicates(int[] nums) {
int count = 1;
int j=1;
for(int i=1;i<nums.length;++i){
if(nums[i] == nums[i-1]){
count++;
} else{
count = 1;
}
if(count <= 2) {
nums[j++] = nums[i];
}
}
return j;
}
}
写法2,挺精妙的
class Solution {
public int removeDuplicates(int[] nums) {
int i = 0;
for (int n : nums)
if (i < 2 || n > nums[i-2])
nums[i++] = n;
return i;
}
}
8. 大数相加，给了两个链表
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> stack1 = new LinkedList<>();
Deque<Integer> stack2 = new LinkedList<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode ans = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
int a = stack1.isEmpty() ? 0:stack1.pop();
int b = stack2.isEmpty() ? 0:stack2.pop();
int cur = a + b + carry;
carry = cur / 10;
cur %= 10;
// head 插法
ListNode curnode = new ListNode(cur);
curnode.next = ans;
ans = curnode;
}
return ans;
}
}
解题思路：借助外来两个栈，后进先出的特性，每一位数相加，注意进位。然后，结果放入新的链表，采用head插入法。
时间复杂度：O(max(m, n))O(max(m,n))，其中 mm 与 nn 分别为两个链表的长度。我们需要遍历每个链表。
空间复杂度：O(m + n)O(m+n)，其中 mm 与 nn 分别为两个链表的长度。这是我们把链表内容放入栈中所用的空间。
逆序处理，似乎一般都会用到栈
