leetcode——链表相关问题
如何实现能将数组转为链表的类
package com.test;
public class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
public static ListNode createList(int[] arr) {
ListNode head = new ListNode(arr[0]);
ListNode pre = head;
for(int i = 1; i < arr.length; i++) {
ListNode node = new ListNode(arr[i]);
pre.next = node;
pre = node;
if(i == arr.length - 1) {
node.next = null;
}
}
return head;
}
public static void printList(ListNode head) {
while(head != null) {
if(head.next != null)
System.out.print(head.val + "->");
else
System.out.println(head.val + "->NULL");
head = head.next;
}
}
}
206. 反转链表
给你单链表的头节点 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
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
思路：有三个指针即可。
class Solution {
public ListNode reverseList(ListNode head) {
// 创建一个虚拟头结点
ListNode prev = null;
ListNode curr = head;
while(curr != null){
// 这代码很有趣啊，就是首尾相接。
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
92. 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
提示：
链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
思路：将要逆序的链表截出来，反转完再接回去。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(501);
dummy.next = head;
ListNode pre = dummy;
// 走到left的前一个
for(int i = 0; i < left - 1; i++){
pre = pre.next;
}
ListNode rightNode = pre;
// 从pre再走right - left + 1,来到right
for(int i = 0; i < right - left + 1; i++){
rightNode = rightNode.next;
}
// 反转链表起点
ListNode leftNode = pre.next;
ListNode curr = rightNode.next;
pre.next = null;
rightNode.next = null;
reverseLinkedList(leftNode);
pre.next = rightNode;
leftNode.next = curr;
return dummy.next;
}
private void reverseLinkedList(ListNode head){
// 也可以使用递归反转一个链表
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}
}
当然上一种方法过于简单粗暴了，还有另一个解法：
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
for(int i = 1; i < left; i++){
pre = pre.next;
}
head = pre.next;
for(int i = left; i < right; i++){
ListNode nex = head.next;
head.next = nex.next;
nex.next = pre.next;
pre.next = nex;
}
return dummy.next;
}
}
83. 删除排序链表中的重复元素
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
返回同样按升序排列的结果链表。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(-101);
dummy.next = head;
ListNode cur = dummy;
while(cur != null){
ListNode next = cur.next;
if(next != null && next.val == cur.val){
cur.next = next.next;
next.next = null;;
}else{
cur = cur.next;
}
}
return dummy.next;
}
}
86. 分隔链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
提示：
链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200
思路：使用两条指针，small和large，将链表分为small和large两条，最后small.next = largeHead.next进行合并。
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode small = new ListNode(0);
ListNode smallHead = small;
ListNode large = new ListNode(0);
ListNode largeHead = large;
while (head != null) {
if (head.val < x) {
small.next = head;
small = small.next;
} else {
large.next = head;
large = large.next;
}
head = head.next;
}
large.next = null;
small.next = largeHead.next;
return smallHead.next;
}
}
2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(-1);
ListNode pre = dummyHead;
int t = 0;
while(l1 != null || l2 != null || t != 0){
if(l1 != null){
t += l1.val;
l1 = l1.next;
}
if(l2 != null){
t += l2.val;
l2 = l2.next;
}
pre.next = new ListNode(t % 10);
pre = pre.next;
t /= 10;
}
return dummyHead.next;
}
}
203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
提示：
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode pre = dummyHead;
ListNode cur = head;
while(cur != null){
if(cur.val == val){
pre.next = cur.next;
cur.next = null;
cur = pre.next;
}else{
cur = cur.next;
pre = pre.next;
}
}
return dummyHead.next;
}
}
- 删除排序链表中的重复元素 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
题目数据保证链表已经按升序排列
思路：没什么技巧，就是判断cur和next是不是相等，相等就删掉next。画图维护好指针就行了。那个else if(next == null）是因为当链表为[1,1]的时候，如果next为null，pre.next没做处理，cur仍然指向1，就会出错。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode pre = dummyHead;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
while(next != null && cur.val == next.val){
cur.next = next.next;
next.next = null;
next = cur.next;
if(next != null && cur.val != next.val){
pre.next = cur.next;
cur.next = null;
cur = pre.next;
next = cur.next;
}else if(next == null){
pre.next = cur.next;
}
}
pre = pre.next;
cur = cur.next;
}
return dummyHead.next;
}
}
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
思路跟合并两个有序数组是一样的。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(-1);
ListNode cur = dummyHead;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
while(l1 != null){
cur.next = l1;
cur = cur.next;
l1 = l1.next;
}
while(l2 != null){
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
return dummyHead.next;
}
}
- 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）
思路：对于这种交换节点的，维护三个指针即可。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode pre = dummyHead;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
if(next != null){
cur.next = next.next;
next.next = pre.next;
pre.next = next;
pre = cur;
}
cur = cur.next;
}
return dummyHead.next;
}
}
25. 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
思路：截出长度为k的链表，反转，再接回去。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode cur = dummy.next;
int count = 0;
while(cur != null) {
ListNode next = cur.next;
ListNode childHead = cur;
ListNode prec = childHead;
count++;
while(cur.next != null) {
count++;
cur = cur.next;
next = cur.next;
prec = cur;
if(count == k) {
prec.next = null;
break;
}
}
if(count == k) {
childHead = reverse(childHead);
pre.next = childHead;
while(childHead.next != null) {
childHead = childHead.next;
}
pre = childHead;
pre.next = next;
cur = next;
count = 0;
}else {
break;
}
}
return dummy.next;
}
private ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
}
147. 对链表进行插入排序
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
难点：插入排序是从第二个开始，每个依次跟前一个作比较，链表不能往前移动。解决的办法就是从前往后遍历。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode prer = dummyHead;
ListNode pre = head;
ListNode cur = head.next;
ListNode curr = head;
while(cur != null){
if(pre.val > cur.val){
curr.next = cur.next;
prer.next = cur;
cur.next = pre;
cur = curr.next;
prer = dummyHead;
pre = dummyHead.next;
}else{
prer = pre;
pre = pre.next;
if(pre == cur){
curr = cur;
cur = cur.next;
prer = dummyHead;
pre = dummyHead.next;
}
}
}
return dummyHead.next;
}
}
148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
// 确定为归并排序（稳定，时间复杂度为O（nlogn））
// 1.递归结束条件
if(head == null || head.next == null)
return head;
// 2.找到链表中间节点并断开&递归下探
ListNode middleNode = findMiddleNode(head);
ListNode rightList = middleNode.next;
middleNode.next = null;
ListNode left = sortList(head);
ListNode right = sortList(rightList);
// 合并
return mergeList(left, right);
}
public ListNode findMiddleNode(ListNode head){
if(head == null || head.next == null)
return head;
ListNode slow = head;
ListNode fast = head.next;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode mergeList(ListNode left, ListNode right){
ListNode dummyHead = new ListNode(-1);
ListNode cur = dummyHead;
while(left != null && right != null){
if(left.val < right.val){
cur.next = left;
left = left.next;
}else{
cur.next = right;
right = right.next;
}
cur = cur.next;
}
cur.next = left != null ? left : right;
return dummyHead.next;
}
}
237. 删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
现有一个链表 – head = [4,5,1,9]，它可以表示为:
示例 1：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2：
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
提示：
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
思路：删除倒数第n个，我们可以维护一个距离（pre到cur的距离为n），因为最后要删除pre，所以pre前一个也得有一个指针。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode pre = dummyHead.next;
ListNode prer = dummyHead;
ListNode cur = head;
for(int i = 0; i < n; i++){
cur = cur.next;
}
while(cur != null){
cur = cur.next;
prer = pre;
pre = pre.next;
}
prer.next = pre.next;
pre.next = null;
return dummyHead.next;
}
}
61. 旋转链表
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
示例 2：
输入：head = [0,1,2], k = 4
输出：[2,0,1]
提示：
- 链表中节点的数目在范围
[0, 500]内 -100 <= Node.val <= 1000 <= k <= 2 * 109
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
// 算出截断的位置，循环将最后一个接到第一个。
if(head == null || head.next == null)
return head;
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode pre = dummyHead;
ListNode cur = dummyHead.next;
int len = 0;
while(cur != null){
len++;
cur = cur.next;
}
k = k % len;
cur = dummyHead.next;
for(int i = 0; i < k; i++){
while(cur.next.next != null){
cur = cur.next;
}
cur.next.next = pre.next;
pre.next = cur.next;
cur.next = null;
cur = dummyHead.next;
}
return dummyHead.next;
}
}
这个方法太暴力了，我们用另一种解法，把链表变成循环链表。然后遍历len - k次（因为截断的位置是后第k个即，len - k）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null)
return head;
ListNode cur = head;
int len = 1;
while(cur.next != null){
len++;
cur = cur.next;
}
cur.next = head;
k = k % len;
int index = len - k;
while(index-- > 0){
cur = cur.next;
}
ListNode newHead = cur.next;
cur.next = null;
return newHead;
}
}
143. 重排链表
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
输入: head = [1,2,3,4]
输出: [1,4,2,3]
示例 2:
输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]
提示：
链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
// 从中间截断，反转后半段，新建链表依次插入。
if(head == null || head.next == null)
return ;
// 快慢指针定位中点
ListNode slowHead = head;
ListNode slow = head;
ListNode fastHead = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
fastHead = slow.next;
slow.next = null;
// 反转fastHead
fastHead = reverse(fastHead);
// 合并
mergeList(slowHead, fastHead);
}
public ListNode reverse(ListNode head){
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
public void mergeList(ListNode l1, ListNode l2){
// 用于指向l1、l2的后一个节点。
ListNode l1_tmp;
ListNode l2_tmp;
while(l1 != null && l2 != null){
l1_tmp = l1.next;
l2_tmp = l2.next;
l1.next = l2;
l1 = l1_tmp;
l2.next = l1;
l2 = l2_tmp;
}
}
}
234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
// 从中间截断，反转后半段，判断
if(head == null || head.next == null)
return true;
// 快慢指针定位中点
ListNode slowHead = head;
ListNode slow = head;
ListNode fastHead = head;
ListNode fast = head.next;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
fastHead = slow.next;
slow.next = null;
// 反转fastHead
fastHead = reverse(fastHead);
ListNode pre = fastHead;
fast = fastHead;
slow = slowHead;
while(fast != null && slow != null){
if(slow.val != fast.val){
return false;
}
slow = slow.next;
fast = fast.next;
}
return true;
}
public ListNode reverse(ListNode head){
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}