算法刷题3-链表章节

3 链表

3.0 链表题目总结

在链表最重要的一个思想：！！！区域指针！！！，理解了这个指针，就能解决百分之90的题目。

3.1 链表的中间节点 ()

1. 问题描述：给定一个头结点为head的非空单列表，放回链表的中间结点。如果有两个中间节点，则返回第二个。
2. 解题思路：双指针-快慢指针
   • 双指针初始指向头结点。
   • 慢指针每次移动一步，快指针每次移动两步，直到快指针指向null，这个时候的慢指针就指向中间位置。
3. 伪代码：
   • fast = head；slow = head；
   • while：fast!=null且fast.next!=null
     • fast = fast.next.next
     • slow = slow.next
   • return slow
4. 时间复杂度O(n)，空间复杂度O(1)

3.2 合并两个升序链表 ()

1. 问题描述：将两个升序链表合并成一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
2. 解题思路：三遍历指针（新链表指针，老链表指针1，老链表指针2）
   • 初始时生成一个新的虚拟头结点，并使得新链表指针cur指向头节点。
   • 老链表指针1指向链表1的头结点，老链表指针2指向链表2的头结点。
   • 不断对指针1和指针2指向的值进行比较
     • 谁小则谁连接到新链表并往后移动一步，直到某个链表被遍历完。
   • 最后将没遍历完的列表连接到新链表后面即可。
3. 伪代码
   • dummy = new Node(-1);cur = dummy;
   • while：list1和list2都不为null
     • if：list1.val小于list2
       • cur.next = list1;
       • list1 = list1.next;
     • else：
       • cur.next = list2;
       • list2 = list2.next;
   • if：list1不为空
     • cur.next = list1;
   • else:
     • cur.next = list2;
   • return dummy.next
4. 时间复杂度O(n)，空间复杂度O(1)

3.3 反转链表 ()

1. 问题描述：给你单链表的头结点head，请你反转链表。
2. 解题思路：递归求解。
   • 递归函数reverse的参数和返回值
     • 参数：当前头结点head
     • 返回值：反转后的头结点root
   • 递归终值：
     • if：当前节点head为null或者head.next为空
       • return head；
   • 单层递归逻辑：
     • nextnode = head.next;
     • root = reverse(nextnode);
     • nextnode.next = head;
     • head.next = null;
     • return root;
3. 伪代码：
   • if：当前节点head为null或者head.next为空
     • return head
   • nextnode = head.next;
     • root = reverse(nextnode);
     • nextnode.next = head;
     • head.next = null;
     • return root;
4. 时间复杂度O(n)，空间复杂度O(n)
   • 空间复杂度主要取决于递归调用的栈空间，最多为 n 层。
5. 衍生问题：
   • 递归求解：
     • 新建一个虚节点，从头遍历链表，使用头插法

3.4 排序链表 ()

1. 问题描述：给一个链表的头结点head，请按升序排列并返回排序后的链表。
2. 解题思路：归并排序+三指针（参考合并两个升序链表）
   • 归并排序
     • 大循环对每个分区的大小sub_length进行循环，以2的倍数增长
       • 初始化排序好的尾节点end指向虚拟头结点dummyHead
       • 使用cur遍历next及以后的数据，即遍历还没有进行排序的区块4。
         • cur指针遍历一次sub_length长度，记录头指针head1，并断开后续连接形成区块2，cur指向新的后继。
         • cur指针再遍历一次sub_length长度，记录头指针head2，并断开后续连接形参区块3，将后继交给next，作为区块4。
         • 对head1和head2进行升序列表合并。返回头节点并接入尾节点end。可以记为区块1.
3. 伪代码：
   • dummy = new Node(-1,head)
   • for：sub_len从1开始，sub_len小于n时，sub_len*=2
     • cur = dummy.next;
     • end = dummy;
     • while：cur不为null
       • //找第一个归并区间
       • head1 = cur;
       • len = 1;
       • while1：len小于sub_len且cur不为null
         • cur = cur.next;
         • len++;
       • //边界情况判断（只分出了第一个区间，第二个区间为空，说明已经排好）
       • if：cur.next为null
         • break;
       • //断开第一个区间并找第二个归并区间
       • head2 = cur.next
       • cur.next = null
       • cur = head2
       • len = 1;
       • while2：len小于sub_len且cur不为null且cur.next不为null
         • cur = cur.next;
         • len++;
       • //正常处理步骤，断开第二个区间，合并两个有序数组，并继续
       • next = cur.next
       • cur.next = null
       • end.next = merge_sort(head1,head2)
       • cur = next;
       • while3：end.next不为空
         • end=end.next
       • //将未排序节点拼回去
       • end.next = cur;
4. 时间复杂度O(nlogn)，空间复杂度O(1)

3.5 重排列表 ()

1. 问题描述：给定一个链表：L0→L1→…→Ln-1→Ln，重排后为L0→Ln→L1→Ln-1→L2→Ln-2→…
2. 解题思路：分拆+反转+拼接
   • 首先寻找到中间节点，然后拆分成前后两个区域。
   • 将后面的区域进行反转。
   • 将前后两个区域从第一个位置一个个拼接。
3. 伪代码：
   • dummy1 = new Node(-1,head)
   • //寻找中间节点
   • fast = dummy1;slow = dummy1;
   • while：fast不为null且fast.next也不为null
     • slow = slow.next;
     • fast = fast.next.next;
   • //断开前后
   • next = slow.next;
   • slow.next = null;
   • //翻转后半部分
   • dummy2 = new Node(-1,reverse(next));
   • dummy = new Node(-1,null);
   • head = dummy;
   • for：i从0不断自增，当dummy1.next!=null或dummy2.next!=null时
     • if：i%2==0
       • head.next = dummy1.next;
       • dummy1.next = dummy1.next.next;
       • head = head.next;
     • else:
       • head.next = dummy2.next;
       • dummy2.next = dummy2.next.next;
       • head = head.next;
   • return dummy.next;
4. 时间复杂度O(n)，空间复杂度O(1)

3.6 旋转链表 ()

1. 问题描述：给定一个链表的头结点head，旋转链表，将链表的每个节点向右移动k个位置。
2. 解题思路：遍历指针*2（先后遍历）
   • 首先获取遍历一次链表，获取链表长度L。
   • 然后前指针和后指针初始位置都为头指针
   • 首先将前指针向前移动k%L次。
   • 然后同时移动前指针和后指针，直到后指针指向最后一个头结点。
   • 将前指针指向头节点，后指针的下一个节点为新的头结点，后指针指向的就是尾节点，将尾节点指向null。
   • 返回头结点。
3. 伪代码：
   • //首先进行边界判断
   • if：head为null
     • return head
   • dummy = new Node(-1,head)
   • n = 0;
   • while：head为null时
     • n++
     • head = head.next
   • slow = dummy;fast = dummy;
   • k %= n
   • while：k–大于0
     • fast=fast.next
   • while：fast.next不为null
     • fast=fast.next
     • slow=slow.next
   • fast.next = dummy.next
   • dummy.next = slow.next
   • slow.next = null
   • return dummy.next
4. 时间复杂度O(n)，空间复杂度O(1)

3.7 两两交换链表中的节点 ()

1. 问题描述：给定一个链表，两两交换相邻的节点，并返回交换后的头结点。
2. 解题思路：递归求解/迭代解法，（迭代算法的话，使用区域指针）
   • 以递归为例子，主要思想是：每次返回交换好的子链表的头结点。
     • 递归终值：因为是两个进行交换，所以终值条件是当前节点或者当前节点的下一个节点为空时，将当前节点返回作为头结点。
     • 递归式： 将当前节点的下一个节点的下一个节点作为头结点递归，获取该节点的后续链表头结点。
     • 递归体：
       • 通过递归式，获取下下一个节点的后续排序好的子链表。
       • 获取当前节点的下一个节点。
       • 将下一个节点指向自己。
       • 将当前节点指向后续链表头结点。
       • 返回下一个节点。（即本次交换后的链表头结点）
3. 伪代码：（以迭代为例）
   • dummy = new Node(-1,head)
   • end = dummy
   • next = dummy
   • cur = head
   • while：cur不为null且cur.next不为null
     • next = cur.next.next
     • //交换节点
     • end.next = cur.next
     • cur.next.next = cur
     • cur.next = next
     • //更新指针位置
     • end = cur
     • cur = next
4. 时间复杂度O(n)，空间复杂度O(1)

3.8 合并k个升序链表 ()

1. 问题描述：给定一个链表数组，每个链表都已经升序排列，请合并在同一个列表并保存升序。
2. 解题思路：递归归并两两列表/迭代使用两个升序列表归并（LC-21）
   • 递归归并：
     • 递归函数mergek的参数和返回值
       • 参数：节点列表lists
       • 返回值：合并后的有序列表头结点root
     • 递归终值：
       • if：lists的长度为0（边界条件）
         • return null
       • if：lists的长度为1
         • return lists[0]
     • 单层递归逻辑：
       • 找到lists的中间索引mid
       • 递归求解左右子数组
       • 合并递归求解出的左右子数组链表，并返回。
3. 伪代码：
   • if：lists的长度为0
     • return null
   • if：lists的长度为1
     • return lists[0]
   • mid = lists.length/2
   • left = mergek(Arrays.copyOfRange(lists,0,mid))
   • right = mergek(Arrays.copyOfRange(lists,mid,lists.length))
   • return merge_sort(right,left)
4. 时间复杂度O(kn*logk)，空间复杂度O(logk)
5. 衍生问题
   • merge_sort函数就是合并两个有序链表

3.9 删除排序链表中的重复元素 ()

1. 问题描述：给定一个排序好的链表，删除所有重复元素，重复元素只保留一个，并返回链表。
2. 解题思路：区域指针+遍历指针
   • 区域指针初始化指向头结点
   • 如果头结点不为空，遍历指针指向下一个节点
   • 当遍历指针指向节点不为空时
     • 判断遍历指针和区域指针是否相等
       • 相等，则遍历指针指向下一个节点
       • 不相等，则将该节点加入区域指针，更新区域指针和遍历指针位置。
3. 伪代码：
   • end = head
   • if：head为null
     • return null
   • cur = head.next
   • while：cur不为null
     • if：cur.val等于end.var
       • cur = cur.next
     • else:
       • end.next = cur;
       • cur = cur.next;
       • end = end.next;
   • end.next = null;
   • return head
4. 时间复杂度O(n)，空间复杂度O(1)

3.10 删除排序链表中的重复元素2 ()

1. 问题描述：给定一个已经排序的链表，删除所有重复元素，不保留重复元素，返回链表。
2. 解题思路：递归/迭代
   • 1. 递归解法
        • 递归终值：
          • 当前头节点或者下一个节点为空，则返回当前头节点。
        • 递归体：
          • 当前头节点和下一个节点是否相同：(即跳过相同的节点，只递归不同的节点)
            • 相同，不断循环遍历，找到不同的节点，返回该不同节点的 递归求解值。
            • 不相同，求解下一个节点的 递归求解值，将当前头节点指向该 递归求解值，返回当前头节点。
   • 2. 迭代求解（区域指针+遍历指针）
        • 设置一个虚拟头结点，和一个循环遍历指针指向它。
        • 判断遍历指针指向的节点的 “下一个节点” 和 “下下个节点” 是否相同。
          • 相同，则记录下相同的值，使用新的遍历指针循环删除值相同的节点，直到新的节点。将遍历指针的下一个节点变为新节点，然后再指向该新节点。
          • 不相同，则遍历指针直接指向该节点。
        • 返回虚拟头结点的下一个节点。
3. 伪代码（以迭代为例）
   • dummy = new Node(-1,head)
   • cur = head; end = dummy;
   • while：cur不为空且cur.next不为空
     • if：cur.val不等于cur.next.val
       • end.next = cur;
       • cur = cur.next;
       • end = end.next;
     • else:
       • temp = cur.var;
       • while2：cur!=null且cur.var不等于temp
         • cur = cur.next;
   • end.next = cur
   • return dummy.next
4. 时间复杂度O(n)，空间复杂度O(1)，对于遍历空间复杂度是O(n)。

3.11 环形链表2 ()

1. 问题描述：给定一个单链表，判断是否有环，如果有环返回环开始的位置，没有则放回null。
2. 解题思路：快慢指针（相遇）+同步指针（相遇）
   • 首先使用快慢指针从头结点开始不断遍历链表，快指针每次移动两步，慢指针每次移动一步。
     • 如果遍历的时候发现有节点指向null，则说明无环。
     • 如果快慢指针相遇了，那么记下相遇位置，作为同步起始点2。
   • 如果有环，则同步指针1从头结点，同步指针2从同步起始点，每次移动一步，直到他们相遇，那么相遇点就是环的起始点，返回相遇点。
3. 伪代码：
   • fast = head; slow = head;
   • while：true
     • if：fast为null或者fast.next为null
       • return null
     • slow = slow.next
     • fast = fast.next.next
     • if2：fast等于slow
       • break;
   • slow = head
   • while2：slow不等于fast
     • slow = slow.next
     • fast = fast.next
   • return slow
4. 时间复杂度O(n)，空间复杂度O(1)

3.12 回文链表 ()

1. 问题描述：给一个链表，判断是否它是否为回文链表，即顺序输出和逆序输出一样。
2. 解题思路：快慢指针（折中拆分）+反转（后半链表）+双指针遍历
   • 首先初始化快慢指针在头结点位置，快指针每次移动两步，慢指针每次移动一步，将整个链表拆成前半和后半链表。
   • 将后半链表进行翻转。
   • 再用两个指针分别遍历前半链表和后半链表对比。
3. 伪代码：
   • dummy = new Node(-1,head)
   • fast = dummy; slow = dummy;
   • while：fast不为null且fast.next不为null
     • slow = slow.next;
     • fast = fast.next.next;
   • fast = reverse(slow.next);
   • slow.next = null;
   • slow = head;
   • while2：fast不为空时
     • if：fast.val不等于slow.val
       • return false
     • fast = fast.next;
     • slow = slow.next;
   • return true;
4. 时间复杂度O(n)，空间复杂度O(1)

3.13 相交链表 ()

1. 问题描述：给定两个单链表，找到他们相交的位置。
2. 解题思路：双指针交叉遍历
   • 两个指针分别指向两个链表的头结点，不断遍历，直到两个指针指向的值相同，返回相同值。
     • 如果其中一个指针遍历完了，则从另一个链表的头结点开始重新遍历。
   • 最后要么两个指针相遇在相交处，要么都分别遍历完了两个链表，值都等于null，即到达链表尾节点。
3. 伪代码：
   • curA = headA; curB = headB;
   • while：curA不等于curB
     • if：curA不为null
       • curA = curA.next;
     • else:
       • curA = headB;
     • if2：curB不为null
       • curB = curB.next;
     • else2:
       • curB = headA;
4. 时间复杂度O(m+n)，空间复杂度O(1)
   • 最差的情况就是两个链表没有交点，最后两个指针都遍历了m+n次（也就是都遍历完了一次两个链表），分别到达尾节点。

3.14 奇偶链表 ()

1. 问题描述：给定一个单链表，奇数位置的结点放在前半，偶数位置的节点放在后半。只能进行原地操作。
2. 解题思路：双指针记尾+双指针记头（也可以叫区域指针）
   • 首先判断边界情况，是否为空或只有一个节点。
   • 初始一个奇头指针和奇数尾指针指向当前头结点，初始化一个偶数头指针和偶数尾指针指向当前节点的下一个节点。
   • 当偶数指针指向的节点不为空且下一个节点也不为空时（即还有奇数节点要排序时）
     • 奇数尾指针指向的节点的下一个节点设为:偶数尾节点的下一个节点。奇数尾指针也指向该节点。
     • 偶数指针指向奇数尾指针指向节点的下一个节点。偶数尾指针也指向该节点。
   • 最后将偶数头指针拼接到奇数尾指针上。
3. 伪代码：
   • dummy1 = new Node(-1); dummy2 = new Node(-1);
   • end1 = dummy1; end2 = dummy2;
   • cur = head;
   • while：cur不为null且cur.next不为null
     • end1.next = cur;
     • end2.next = cur.next;
     • //更新指针位置
     • cur = cur.next.next;
     • end1 = end1.next;
     • end2 = end2.next;
   • end1.next = cur;
   • end2.next = null;
   • if：end1.next为null
     • end1.next = dummy2.next;
   • else:
     • end1.next.next = dummy2.next;
   • return dummy1.next;
4. 时间复杂度O(n)，空间复杂度O(1)

3.15 移除链表元素 ()

1. 问题描述：给定一个单链表，删除链表中值为val的节点并返回新的头节点。
2. 解题思路：区域指针+遍历指针
   • 初始化两个指针，一个指针为遍历指针，从头节点开始，一个是有效链表尾指针，指向虚拟头节点。
   • 不断使用遍历指针遍历链表（每次循环结束时，遍历指针指向下一个节点），看当前的值是否为val
     • 不是，将有效链表尾指针=遍历指针。
     • 是，则将有效链表尾指针指向的节点的下一个节点指向遍历指针的下一个节点（即跳过当前要删除的节点）。
3. 伪代码：
   • dummy = new Node(-1,head);
   • cur = dummy.next;
   • end = dummy;
   • while：cur不为null
     • if：cur.val不等于val
       • end.next = cur;
       • end = end.next;
     • cur = cur.next;
   • end.next = null;
   • return dummy.next;
4. 时间复杂度O(n)，空间复杂度O(1)

3.16 k个一组翻转链表 ()

1. 问题描述：给定一个链表，每k个节点一组进行翻转，返回新的链表。
2. 解题思路：区域指针
   • 初始化一个虚拟头节点指向原头节点，一个遍历指针cur，一个已完成翻转区域尾节点end，一个未翻转区域头节点next。
   • 循环翻转链表，直到cur指向的节点为实际尾节点。
     • 首先循环移动cur，直到移动了k个节点，或者当前节点为空时结束。
     • 如果cur不为空，next指向cur的下一个节点。如果cur为空则说明不足k个，直接跳出循环。
     • 将选出的k个节点拆出来进行翻转，然后拼接到end后。
     • 更新end位置，更新cur位置。
3. 伪代码：
   • dummy = new Node(-1,head);
   • end = dummy; next = dummy.next; cur = next;
   • while：cur不为null时
     • i = 1;
     • for：i小于k且cur.next不为null，i++
       • cur = cur.next;
     • if：i小于k
       • break;
     • //保存未翻转区域，断开需要翻转区域
     • next = cur.next;
     • cur.next = null;
     • end.next = reverse(end.next);
     • //更新指针位置
     • while2：end.next不为null时
     • end = end.next;
   • cur = next;
   • //拼接回去
   • end.next = next;

• return dummy.next;

4. 时间复杂度O(n)，空间复杂度O(1)