算法集锦（NO.3）
链表
加快进度
两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）
方法一：
递归：既然是节点之间的两两互换，可用递归至底层进行合并。
class Solution {
public ListNode swapPairs(ListNode head) {
//当当前节点或者下一节点为空的时候，这就说明接下来没有组合进行合并。
if (head == null || head.next == null) {
return head;
}
//设立新的指针空间（2节点）来保存当前节点的下一个节点
ListNode newHead = head.next;
//使其递归，因为此时的1节点，进过互换后为2节点，但是两节点的互换并不影响后面链表的顺序。
head.next = swapPairs(newHead.next);
//将2节点的指针指向1节点，进行两个节点间的互换
newHead.next = head;
//返回此时在前的2节点
return newHead;
}
}
时间复杂度O（n）
空间复杂度O（n）
方法二：
迭代：该思想为直接在链表上进行互换操作。大致思想为，temp为前置节点，node1为1节点，node2为2节点，让前置节点的指针指向node2，
node1的指针指向node2后的链表，node2的指针指向node1。然后前置节点更新为node1。
class Solution {
public ListNode swapPairs(ListNode head) {
//设立哨兵头节点，和其进行操作的temp节点
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode temp = dummyHead;
//前置节点temp
while (temp.next != null && temp.next.next != null) {
//1节点node1
ListNode node1 = temp.next;
//2节点node2
ListNode node2 = temp.next.next;
//前置指针指向node2
temp.next = node2;
//node1的指针指向node2后面的链表
node1.next = node2.next;
//node2的指针指向node1
node2.next = node1;
//前置指针更新为node1
temp = node1;
}
return dummyHead.next;
}
}
K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
示例 3：
输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]
示例 4：
输入：head = [1], k = 1
输出：[1]
提示：
列表中节点的数量在范围 sz 内
1 <= sz <= 5000
0 <= Node.val <= 1000
1 <= k <= sz
此题相较于上题为
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head==null||k<2){
return head;
}
//此处设置统计每次k长度的运行后的终止节点tempNext,该k链表区间的前置节点temp
ListNode node =new ListNode(0,head);
ListNode temp =node;
ListNode tempNext =node;
int n=0;
//进行k段的切割，对k段内的节点进行反转
while(temp.next!=null){
//对后续链表进行k长度的切割
while(n<k&&tempNext.next!=null){
tempNext = tempNext.next;
n++;
}
//当后续链表长度小于k时，说明反转结束
if(n<k){
break;
}
//用temp这个前置节点来对其后面1个k段进行反转
temp.next = reverseList(temp.next,k);
//前置节点的后移，终止于下一次k段反转的前置，并且n清零
while(n>0){
temp = temp.next;
n--;
}
}
return node.next;
}
//对前k个节点进行反转
public ListNode reverseList(ListNode node,int k){
ListNode nodeNew = new ListNode(0);
ListNode temp = nodeNew;
int n=0;
//尾插法进行链表的反转
while(n<k){
if(n==0){
temp.next=new ListNode(node.val);
node=node.next;
n++;
}else{
//反转核心操作，具体请看下一题
ListNode tempNext = temp.next;
temp.next = new ListNode(node.val);
node =node.next;
temp.next.next = tempNext;
n++;
}
}
while(temp.next!=null){
temp=temp.next;
}
temp.next=node;
return nodeNew.next;
}
}
反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
方法1:
迭代：
用一个辅助空链表来存放链表当前节点，并且链表指针后移。每次辅助链表进行存放时，都用链表节点来指向辅助链表，通过辅助链表头指针的更新操作来实现迭代节点的保存。
class Solution {
public ListNode reverseList(ListNode head) {
//设立空指针prev来进行迭代指针的存放
ListNode prev = null;
ListNode curr = head;
//头插法进行指针的插入操作
while (curr != null) {
//将链表的子链表进行保存
ListNode next = curr.next;
//将链表的当前节点指向辅助链表，可以实现反转
curr.next = prev;
//辅助链表头节点的更新，保存每次链表的节点
prev = curr;
//链表指针后移
curr = next;
}
return prev;
}
}
方法二：
递归
class Solution {
public ListNode reverseList(ListNode head) {
//后续节点为空的时候，就可以返回当前节点。
if (head == null || head.next == null) {
return head;
}
//newhead来直入最底层节点，进行保存，层层递归来进行节点的不断保存
ListNode newHead = reverseList(head.next);
//将前后节点指向进行顺序两两互换
head.next.next = head;
head.next = null;
return newHead;
}
}
删除排序链表中的重复元素
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
返回同样按升序排列的结果链表。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列
删除排序链表中的重复元素 II
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列
方法：可视有3个节点，分别为当前节点，当前节点的前置节点，当前节点的后置节点。当当前节点不为空，并且，其不等于前置节点和后置节点时，进行节点后移，否则进行该节点的删除。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
//如果输入head为空，则直接返回
if (head == null) {
return head;
}
//设立哨兵head
ListNode dummy = new ListNode(0, head);
//cur进行节点的操作
ListNode cur = dummy;
//当其后续节点和
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
int x = cur.next.val;
while (cur.next != null && cur.next.val == x) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
时间复杂度O（n），空间复杂度O（1）