链表（牛客）
题目来自牛客题目库 算法篇面试必刷TOP101。
BM1 反转链表(简单)
题目
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围： 0≤n≤1000
要求：空间复杂度O(1) ，时间复杂度O(n) 。
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
示例：
示例1：
输入：{1,2,3}
返回值：{3,2,1}
示例2：
输入：{}
返回值：{}
解法1 遍历
创建新的头节点，遍历老链表，将老链表的节点反转，同时移动新的头节点到老链表的尾部。
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode newHead = null;
while(head != null)
{
// 保存老链表的下一个节点
ListNode temp = head.next;
// 将老链表当前节点添加到新链表头部
head.next = newHead;
// 新链表头节点为刚刚添加的节点
newHead = head;
// 将老链表的当前节点移动到下一个
head = temp;
}
return newHead;
}
}
解法2 栈
遇到反转想到用栈。
import java.util.Stack;
public class Solution {
public ListNode ReverseList(ListNode head) {
Stack<ListNode> stack = new Stack<>();
while(head != null)
{
stack.push(head);
head = head.next;
}
if(stack.isEmpty())
{
return null;
}
ListNode node = stack.pop();
ListNode dummy = node;
while(!stack.empty())
{
ListNode tempNode = stack.pop();
node.next = tempNode;
node = node.next;
}
node.next = null; // 防止成环
return dummy;
}
}
BM2 链表内指定区间反转(中等)
题目
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度O(1)。 例如： 给出的链表为 1→2→3→4→5→NULL, m=2,n=4, 返回 1→4→3→2→5→NULL.
数据范围： 链表长度 0<size≤1000，0<m≤n≤size，链表中每个节点的值满足∣val∣≤1000
要求：时间复杂度O(n) ，空间复杂度O(n)
进阶：时间复杂度O(n)，空间复杂度O(1)
示例：
示例1：
输入：{1,2,3,4,5},2,4
返回值：{1,4,3,2,5}
示例2：
输入：{5},1,1
返回值：{5}
解法 迭代
迭代。
public class Solution {
public ListNode reverseBetween (ListNode head, int m, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
// 将cur移动到反转位置m
for(int i = 1; i < m; i++)
{
pre = cur;
cur = cur.next;
}
// 反转从m到n的节点
for(int i = m; i < n; i++)
{
ListNode temp = cur.next;
cur.next = temp.next;
temp.next = pre.next; // 不能是cur，只能是pre.next
pre.next = temp;
}
return dummy.next;
}
}
BM3 链表中的节点每k个一组翻转(中等)
题目
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样 你不能更改节点中的值，只能更改节点本身。
数据范围： 0≤n≤2000 ，1≤k≤2000 ，链表中每个元素都满足0≤val≤1000 要求空间复杂度 O(1)，时间复杂度O(n)
例如：
给定的链表是 1→2→3→4→5
对于k=2 , 你应该返回 2→1→4→3→5
对于k=3 , 你应该返回 3→2→1→4→5
示例1
输入：{1,2,3,4,5},2
返回值：{2,1,4,3,5}
示例2
输入：{},1
返回值：{}
解法 栈
每组用栈储存k个节点，反转后连接下一组节点。如果每组不足k个节点，直接返回头节点。
public class Solution {
public ListNode reverseKGroup (ListNode head, int k) {
Stack<ListNode> stack = new Stack<>();
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
// pre是上一组的尾节点，pre.next为下一组的头节点
ListNode pre = dummyHead;
int count = k;
while (true) {
ListNode cur = head;
for (int i = 0; i < count; i++) {
// 节点数目不足，直接返回
if (cur == null) {
return dummyHead.next;
}
// 入栈
stack.push(cur);
cur = cur.next; // for循环结束后，cur指向下一组的头节点
}
while (!stack.isEmpty()) {
// 将栈中节点接在尾节点后，实现反转
pre.next = stack.pop();
pre = pre.next; // 栈为空时，pre指向当前组的尾节点
}
pre.next = cur;
head = cur;
}
}
}
BM4 合并两个排序的链表(简单)
题目
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围：0≤n≤1000，−1000≤节点值≤1000 要求：空间复杂度O(1)，时间复杂度 O(n)
如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：
或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：
示例：
示例1：
输入：{1,3,5},{2,4,6}
返回值：{1,2,3,4,5,6}
示例2：
输入：{},{}
返回值：{}
示例3：
输入：{-1,2,4},{1,3,4}
返回值：{-1,1,2,3,4,4}
解法 遍历
比较两个list的头节点的值，选更小的加入到新链表的尾部。
public class Solution {
public ListNode Merge(ListNode list1, ListNode list2) {
ListNode dummyHead = new ListNode(-1);
ListNode cur = dummyHead;
// 比较两个list的头节点的值，选更小的加入到新链表的尾部
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
cur.next = list1;
list1 = list1.next;
cur = cur.next;
} else {
cur.next = list2;
list2 = list2.next;
cur = cur.next;
}
}
// 一个链表遍历结束后，将另一个链表的剩余节点添加到新链表的尾部
if (list1 != null) {
cur.next = list1;
} else {
cur.next = list2;
}
return dummyHead.next;
}
}
BM5 合并k个已排序的链表(较难)
题目
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围：节点总数 0≤n≤5000，每个节点的val满足∣val∣<=1000
要求：时间复杂度 O(nlogn)
示例：
示例1：
输入：[{1,2,3},{4,5,6,7}]
返回值：{1,2,3,4,5,6,7}
示例2：
输入：[{1,2},{1,4,5},{6}]
返回值：{1,1,2,4,5,6}
解法 归并
- 终止条件： 划分的时候直到左右区间相等或左边大于右边。
- 返回值： 每级返回已经合并好的子问题链表。
- 本级任务： 对半划分，将划分后的子问题合并成新的链表。
import java.util.*;
public class Solution {
// 两链表合并排序，同上题
ListNode merge(ListNode list1, ListNode list2)
{
ListNode dummyHead = new ListNode(-1);
ListNode cur = dummyHead;
while(list1 != null && list2 != null)
{
if(list1.val < list2.val)
{
cur.next = list1;
list1 = list1.next;
cur = cur.next;
}
else{
cur.next = list2;
list2 = list2.next;
cur = cur.next;
}
}
if(list1 != null)
cur.next = list1;
if(list2 != null)
cur.next = list2;
return dummyHead.next;
}
// 划分合并区间
ListNode divideMerge(ArrayList<ListNode> lists, int left, int right)
{
// 左端点大于右端点，返回空
if(left > right)
return null;
// 只有一个链表
else if(left == right)
return lists.get(left);
// 大于一个链表，先分再合并
int mid = (left + right) / 2;
return merge(divideMerge(lists, left, mid), divideMerge(lists, mid+1, right));
}
// lists.size()个链表归并排序
public ListNode mergeKLists(ArrayList<ListNode> lists) {
return divideMerge(lists, 0, lists.size() - 1);
}
}
BM6 判断链表中是否有环(简单)
题目
判断给定的链表中是否有环。如果有环则返回true，否则返回false。
数据范围：链表长度 0≤n≤10000，链表中任意节点的值满足 ∣val∣<=100000
要求：空间复杂度O(1)，时间复杂度 O(n)
输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。
例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：
可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。
示例：
示例1：
输入：{3,2,0,-4},1
返回值：true
说明：第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true
示例2：
输入：{1},-1
返回值：false
说明：第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false
示例3：
输入：{-1,-7,7,-4,19,6,-9,-5,-2,-5},6
返回值：true
解法 双指针
快指针一次走两个节点，慢指针一次走一个节点。如果两指针相遇，则有环；如果快指针遍历结束，则无环。
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null)
return false;
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null)
{
fast = fast.next.next;
slow = slow.next;
if(fast == slow)
return true;
}
return false;
}
}
BM7 链表中环的入口结点(中等)
题目
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
数据范围：0n≤10000，1<=结点值<=10000
要求：空间复杂度O(1)，时间复杂度O(n)
例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：
可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
输入描述：
输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
返回值描述：
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
示例：
示例1：
输入：{1,2},{3,4,5}
返回值：3
说明：返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3
示例2：
输入：{1},{}
返回值："null"
说明：没有环，返回对应编程语言的空结点，后台程序会打印"null"
示例3：
输入：{},{2}
返回值：2
说明：环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2
解法 双指针
先使用快慢指针判断有没有环，找到两个指针相遇的节点。将快指针指向链表头节点，慢指针仍指向相遇节点，两个指针每步移动一个节点，相遇位置为环的入口。
public class Solution {
//判断是否有环，有环返回快慢指针相遇位置，无环返回null
ListNode hasCycle(ListNode pHead)
{
if(pHead == null)
return null;
ListNode fast = pHead;
ListNode slow = pHead;
while(fast != null && fast.next != null)
{
fast = fast.next.next;
slow = slow.next;
if(fast == slow)
return slow;
}
return null;
}
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode slow = hasCycle(pHead);
if(slow == null)
return null;
ListNode fast = pHead;
while(fast != slow)
{
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
BM8 链表中倒数最后k个结点(简单)
题目
输入一个长度为 n 的链表，设链表中的元素的值为 a~i~ ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。
数据范围：0≤n≤10^5^，0≤a~i~≤10^9^，0≤k≤10^9^
要求：空间复杂度 O(n)，时间复杂度O(n)
进阶：空间复杂度O(1)，时间复杂度O(n)
例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。
示例：
示例1：
输入：{1,2,3,4,5},2
返回值：{4,5}
说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。
示例2：
输入：{2},8
返回值：{}
解法1 栈
将链表节点入栈，出栈第k个节点。
import java.util.*;
public class Solution {
public ListNode FindKthToTail (ListNode pHead, int k) {
if(k == 0)
return null;
Stack<ListNode> stack = new Stack<>();
ListNode cur = pHead;
while(cur != null)
{
stack.push(cur);
cur = cur.next;
}
for(int i = 0; i < k - 1; i++)
{
if(stack.empty())
return null;
stack.pop();
}
if(stack.empty())
return null;
return stack.pop();
}
}
解法2 遍历
遍历两遍。第一遍统计链表长度n，第二遍找到第n-k个节点。
import java.util.*;
public class Solution {
public ListNode FindKthToTail (ListNode pHead, int k) {
int n = 0;
ListNode p = pHead;
//遍历链表，统计链表长度
while(p != null){
n++;
p = p.next;
}
//长度过小，返回空链表
if(n < k)
return null;
p = pHead;
//遍历n-k次
for(int i = 0; i < n - k; i++)
p = p.next;
return p;
}
}
解法3 双指针
- step 1：准备一个快指针，从链表头开始，在链表上先走k步。
- step 2：准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是k。
- step 3：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数k个元素的位置。
import java.util.*;
public class Solution {
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
if(k == 0)
return null;
ListNode fast = pHead;
for(int i = 0; i < k; i++)
{
if(fast != null)
fast = fast.next;
else
return null;
}
ListNode slow = pHead;
while(fast != null)
{
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
BM9 删除链表的倒数第n个节点(中等)
题目
给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如，
给出的链表为: 1→2→3→4→5, n=2.
删除了链表的倒数第 n 个节点之后,链表变为1→2→3→5.
数据范围： 链表长度0≤n≤1000，链表中任意节点的值满足0≤val≤100
要求：空间复杂度O(1)，时间复杂度O(n)
备注：
题目保证 n 一定是有效的
示例：
输入：{1,2},2
返回值：{2}
解法1 遍历
思路同上BM8。
import java.util.*;
public class Solution {
public ListNode removeNthFromEnd (ListNode head, int n) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode cur = dummyHead;
int length = 0;
// 遍历计算链表长度length
while(cur.next != null)
{
cur = cur.next;
length++;
}
cur = dummyHead;
// 链表长度减n就是要删除的位置
for(int i = 0; i < length - n; i++)
{
cur = cur.next;
}
cur.next = cur.next.next;
return dummyHead.next;
}
}
解法2 双指针
思路同上BM8.
快指针从头先走n，慢指针此时再从头走。当快指针走完的时候，慢指针的位置就是要删除的位置。
import java.util.*;
public class Solution {
public ListNode removeNthFromEnd (ListNode head, int n) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode fast = dummyHead;
for(int i = 0; i < n; i++)
{
fast = fast.next;
}
ListNode slow = dummyHead;
while(fast.next != null)
{
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
}
BM10 两个链表的第一个公共结点(简单)
题目
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
数据范围：n≤1000 要求：空间复杂度O(1)，时间复杂度O(n)
例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
输入描述：
输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。
返回值描述：
返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。
示例：
示例1：
输入：{1,2,3},{4,5},{6,7}
返回值：{6,7}
说明：第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分。这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的。
示例2：
输入：{1},{2,3},{}
返回值：{}
说明：2个链表没有公共节点 ,返回null，后台打印{}
解法 双指针
cur1指针从头遍历链表1，遍历结束后，从头遍历链表2；
cur2指针从头遍历链表2，遍历结束后，从头遍历链表1；
两指针相遇位置为重复的第一个公共节点。
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode cur1 = pHead1;
ListNode cur2 = pHead2;
while (cur1 != cur2) {
cur1 = (cur1 == null) ? pHead2 : cur1.next;
cur2 = (cur2 == null) ? pHead1 : cur2.next;
}
return cur1;
}
}
BM11 链表相加(二)(中等)
题目
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：0≤n,m≤1000000，链表任意值0≤val≤9 要求：空间复杂度O(n)，时间复杂度O(n)
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
示例：
示例1：
输入：[9,3,7],[6,3]
返回值：{1,0,0,0}
示例2：
输入：[0],[6,3]
返回值：{6,3}
解法 反转链表
反转两个链表，按节点依次相加。最后把结果链表反转。
import java.util.*;
public class Solution {
public ListNode reverseList(ListNode head){
// 处理空链表不要忘
if(head == null)
return null;
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
// pre是反转后链表的头节点
return pre;
}
public ListNode addInList (ListNode head1, ListNode head2) {
if(head1 == null)
return head2;
if(head2 == null)
return head1;
// 反转链表
head1 = reverseList(head1);
head2 = reverseList(head2);
// 设置进位
int carry = 0;
// 初始化结果链表，不能赋值null，只能new
ListNode newHead = new ListNode(-1);
ListNode cur = newHead;
// 相加
while(head1 != null || head2 != null || carry != 0){
// 将链表当前节点的值赋给int类型的val
int val1 = head1 == null ? 0 : head1.val;
int val2 = head2 == null ? 0 : head2.val;
int temp = val1 + val2 + carry;
carry = temp / 10;
temp = temp % 10;
// 将当前位的计算结果加到结果链表的尾部
cur.next = new ListNode(temp);
cur = cur.next;
if(head1 != null)
head1 = head1.next;
if(head2 != null)
head2 = head2.next;
}
return reverseList(newHead.next);
}
}
BM12 单链表的排序(中等)
题目
给定一个节点数为n的无序单链表，对其按升序排序。
数据范围：0<n≤100000，保证节点权值在[10^-9^, 10^9^]之内。
要求：空间复杂度O(n)，时间复杂度O(nlogn)
示例：
示例1：
输入：[1,3,2,4,5]
返回值：{1,2,3,4,5}
示例2：
输入：[-1,0,-2]
返回值：{-2,-1,0}
解法1 归并排序
找到中间个元素的前一个节点，将其断开，就可以将链表分成两个子链表，然后继续划分，直到最小，然后往上依次合并。
- 终止条件： 当子链表划分到为空或者只剩一个节点时，不再继续划分，往上合并。
- 返回值： 每次返回两个排好序且合并好的子链表。
- 本级任务： 找到这个链表的中间节点，从前面断开，分为左右两个子链表，进入子问题排序。
import java.util.*;
public class Solution {
// 有序合并两个有序链表
ListNode merge(ListNode phead1, ListNode phead2){
if(phead1 == null)
return phead2;
if(phead2 == null)
return phead1;
ListNode dummyHead = new ListNode(-1);
ListNode cur = dummyHead;
while(phead1 != null && phead2 != null)
{
if(phead1.val <= phead2.val){
cur.next = phead1;
phead1 = phead1.next;
}
else {
cur.next = phead2;
phead2 = phead2.next;
}
cur = cur.next;
}
if(phead1 != null)
cur.next = phead1;
if(phead2 != null)
cur.next = phead2;
return dummyHead.next;
}
// 划分链表直到有序
public ListNode sortInList (ListNode head) {
// 当链表为空或者只有一个节点时，链表有序，程序return
if(head == null || head.next == null)
return head;
ListNode left = head;
ListNode mid = head.next;
ListNode right = head.next.next;
// 令right指向链表末尾，此时mid指向链表中间
while(right != null && right.next != null){
left = left.next;
mid = mid.next;
right = right.next.next;
}
left.next = null;
return merge(sortInList(head),sortInList(mid));
}
}
解法2 转化为数组
链表转化为数组，对数组排序，再转化为链表。
import java.util.*;
public class Solution {
public ListNode sortInList (ListNode head) {
ArrayList<Integer> arr = new ArrayList();
ListNode cur = head;
while(cur != null){
arr.add(cur.val);
cur = cur.next;
}
// 数组排序，注意写法
Collections.sort(arr);
cur = head;
for(int i = 0; i < arr.size(); i++)
{
// 注意获取数组元素的写法
cur.val = arr.get(i);
cur = cur.next;
}
return head;
}
}
BM13 判断一个链表是否为回文结构(简单)
题目
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 0≤n≤10^5^，链表中每个节点的值满足 ∣val∣≤10^7^
示例：
示例1：
输入：{1}
返回值：true
示例2：
输入：{2,1}
返回值：false
说明：2->1
示例3：
输入：{1,2,2,1}
返回值：true
说明：1->2->2->1
解法1 栈
将一半节点入栈，匹配后一半节点。
import java.util.*;
public class Solution {
public boolean isPail (ListNode head) {
// 空链表和只有一个节点的链表是回文结构
if(head == null || head.next == null)
return true;
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode cur = dummyHead;
// 计算节点数目
int num = 0;
while(cur.next != null)
{
num++;
cur = cur.next;
}
Stack<ListNode> stk = new Stack();
cur = head;
// 将一半节点入栈
for(int i = 1; i <= num / 2; i++)
{
stk.push(cur);
cur = cur.next;
}
// 如果是奇数个节点，跳过中间的节点
if(num % 2 == 1)
cur = cur.next;
while(!stk.empty())
{
// 弹出栈顶节点，将栈顶节点值和当前节点值匹配，存在不匹配则不是回文结构
ListNode node = stk.pop();
if(node.val != cur.val)
return false;
cur = cur.next;
}
// 栈中节点匹配完毕，则是回文结构
return true;
}
}
用栈的另一种思路：将链表节点全部入栈，然后从头匹配链表节点。即逆序匹配。
解法2 双指针、反转链表
用双指针找到链表中点，然后反转后半个链表，再比对。
代码略。
BM14 链表的奇偶重排(中等)
题目
给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。
数据范围：节点数量满足0≤n≤10^5^，节点中的值都满足0≤val≤1000
要求：空间复杂度O(n)，时间复杂度O(n)
示例：
示例1：
输入：{1,2,3,4,5,6}
返回值：{1,3,5,2,4,6}
说明：1->2->3->4->5->6->NULL
重排后为1->3->5->2->4->6->NULL
示例2：
输入：{1,4,6,3,7}
返回值：{1,6,7,4,3}
说明：1->4->6->3->7->NULL
重排后为1->6->7->4->3->NULL
奇数位节点有1,6,7，偶数位节点有4,3。重排后为1,6,7,4,3
备注：链表长度不大于200000。每个数范围均在int内。
解法1 队列
(自解，解法2较优)用两个队列分别储存奇偶节点，然后接在新链表后。
import java.util.*;
public class Solution {
public ListNode oddEvenList (ListNode head) {
if(head == null)
return null;
// 节点数目
int count = 1;
ListNode cur = head;
// 用队列存储
Queue<ListNode> odd = new LinkedList<ListNode>();
Queue<ListNode> even = new LinkedList<ListNode>();
while(cur != null)
{
if(count % 2 == 1){
odd.add(cur);
}
else if(count % 2 == 0){
even.add(cur);
}
count++;
cur = cur.next;
}
ListNode dummyHead = new ListNode(-1);
ListNode newCur = dummyHead;
// 将奇偶节点分别接在新链表后
while(!odd.isEmpty()){
newCur.next = odd.remove();
newCur = newCur.next;
}
while(!even.isEmpty()){
newCur.next = even.remove();
newCur = newCur.next;
}
// 链表最后一个节点一定是null，不加这一行报错
newCur.next = null;
return dummyHead.next;
}
}
解法2 双指针
奇偶双指针。
import java.util.*;
public class Solution {
public ListNode oddEvenList (ListNode head) {
if(head == null)
return null;
ListNode odd = head;
ListNode even = head.next;
// 记录even的头节点，便于连接在odd的尾部
ListNode evenHead = even;
while(even != null && even.next != null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
BM15 删除有序链表中重复的元素-I(简单)
题目
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次 例如： 给出的链表为1→1→2,返回1→2. 给出的链表为1→1→2→3→3,返回1→2→3.
数据范围：链表长度满足 0≤n≤100，链表中任意节点的值满足∣val∣≤100
进阶：空间复杂度O(1)，时间复杂度O(n)
示例：
示例1：
输入：{1,1,2}
返回值：{1,2}
示例2：
输入：{}
返回值：{}
解法 双指针
快指针比慢指针快一个节点。如果快慢指针指向节点的值相同，则将快指针向后移动一个节点；否则快慢指针都向后移动一个节点。
import java.util.*;
public class Solution {
public ListNode deleteDuplicates (ListNode head) {
if (head == null || head.next == null)
return head;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null) {
if (slow.val == fast.val) {
fast = fast.next;
slow.next = fast;
}
else {
fast = fast.next;
slow = slow.next;
}
}
return head;
}
}
另解：不用slow和fast两个指针，用cur和cur.next也可以。
BM16 删除有序链表中重复的元素-II(中等)
题目
给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。 例如： 给出的链表为1→2→3→3→4→4→5, 返回1→2→5. 给出的链表为1→1→1→2→3, 返回2→3.
数据范围：链表长度0≤n≤10000，链表中的值满足 ∣val∣≤1000
要求：空间复杂度O(n)，时间复杂度 O(n)
进阶：空间复杂度O(1)，时间复杂度O(n)
解法 迭代
思路同上题BM15，用虚拟头节点。
import java.util.*;
public class Solution {
public ListNode deleteDuplicates (ListNode head) {
if (head == null || head.next == null)
return head;
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode cur = dummyHead;
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
int num = cur.next.val;
// 下一行while语句中的cur.next != null一定要加上
while (cur.next != null && cur.next.val == num) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummyHead.next;
}
}
总结
双指针、迭代最常用，也见栈和队列数据结构，偶有难题需要归并思想。