【算法提升—力扣每日一刷】五日总结【12/06--12/10】

给你单链表的头节点 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//反转链表public ListNode reverseList1(ListNode o1) {ListNode n1 = null;//新链表的头节点ListNode p = o1;//原来链表的头结点while (p != null) {n1 = new ListNode(p.val, n1);p = p.next;}return n1;}//方法2 面向对象，List类在最下方public ListNode reverseList2(ListNode o1) {//创建一个链表，将o1的值赋值给链表List list_old = new List(o1);//创建一个新的链表，初始头节点为nullList list_new = new List(null);//当链表头节点不为空时，循环while (list_old.head != null) {//将链表头节点删除，并赋值给headListListNode headList = list_old.removeHeadList();//将headList添加到新链表的头部list_new.addHeadList(headList);}//返回新链表的头节点return list_new.head;}//方法3 - 递归// 递归调用reverseList函数，传入参数o1.next，返回反转后的链表public ListNode reverseList3(ListNode o1) {if (o1==null||o1.next == null) {return o1;}ListNode last = reverseList(o1.next);o1.next.next = o1;o1.next = null;return last;}//方法4public ListNode reverseList4(ListNode o1){//判断边界   1.空链表   2.只有一个节点的链表   ->都将o1输出即可if(o1==null||o1.next==null){return o1;}ListNode o2 = o1.next;ListNode n1 = o1;while (o2!=null){o1.next = o2.next;o2.next = n1;n1 = o2;o2 = o1.next;}return n1;}//方法5public ListNode reverseList(ListNode o1){//判断边界条件 1.链表为空   2.链表只有一个节点if(o1==null||o1.next==null){return o1;}ListNode n1 = null;while (o1!= null){ListNode o2 = o1.next;o1.next = n1;n1 = o1;o1 = o2;}return n1;}//链表static class List {//链表头节点ListNode head;public List(ListNode head) {this.head = head;}/*** 链表头部添加节点* @param node 待添加节点*/public void addHeadList(ListNode node) {//将添加的节点指向链表头节点node.next = head;//将添加的节点赋值给链表头节点head = node;}/*** 链表头部删除节点* @return 删除的节点*/public ListNode removeHeadList() {//将链表头节点赋值给head_oldListNode head_old = head;//当链表头节点不为空时，循环if (head_old != null) {//将链表头节点指向下一个节点head = head_old.next;}//返回删除的节点return head_old;}}/**  非题解* Leetcode 很多链表题目用到的节点类*/
public class ListNode {public int val;public ListNode next;public ListNode(int val, ListNode next) {this.val = val;this.next = next;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder(64);sb.append("[");ListNode p = this;while (p != null) {sb.append(p.val);if (p.next != null) {sb.append(",");}p = p.next;}sb.append("]");return sb.toString();
//        return String.valueOf(this.val);}public static ListNode of(int... elements) {if (elements.length == 0) {return null;}ListNode p = null;for (int i = elements.length - 1; i >= 0; i--) {p = new ListNode(elements[i], p);}return p;}
}

1. 方法一：直接创建新的链表，遍历旧的链表给新链表的节点赋值，并把新节点不断插入到新链表的头部，实现链表反转 ~~优点：~~易于思考和理解，思路较为简单 ~~缺点：~~无法重用节点，需要建立新的链表节点，比较浪费空间

2. 方法二：利用面向对象的思想，给链表建立一个外部容器，可以在容器中定义操作链表的一些方法，比如上面代码中写道的：删除头结点，从头部插入节点等…建立两个链表容器，一个用题目所给的节点作为头结点，另一个头结点为空，每次将旧链表的头结点删除并定义一个指针记录被删除节点，然后将被删除节点插入到新链表的头部，实现链表反转 ~~优点：~~不需要建立新的节点，可以重用旧的节点，节省空间 ~~缺点：~~代码量比较多

3. 方法三：利用递归的方式，先递归找到最后一个节点，利用递归的特点，在弹栈时就相当于逆向遍历链表，可以对链表实现逆向操作，在弹栈时，实现将当前节点的下一个节点的的下一个节点指向当前节点，实现相邻两个节点的反转，最终实现链表反转。~~优点：~~代码量少，代码看着简洁而优雅

~~缺点：~~对递归不熟悉的小伙伴理解上有难度

4. 方法四：相当于用两个指针模拟出两个链表，实际上在操作一个链表，其中一个指针始终指向新链表的头部，另一个指针始终指向旧链表的头部，不断将旧链表的第二个节点指向新链表的头部，指针回位，循环操作，实现链表反转 ~~优点：~~代码量少 ~~缺点：~~指针太多，并不好理解

5. 方法五：和方法二在思想上有异曲同工之妙，但是更面向过程

~~优点：~~代码量少 ~~缺点：~~指针太多，并不好理解

给你一个链表的头节点 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

	//方法一，定义两个指针循环遍历链表public ListNode removeElements1(ListNode head, int val) {ListNode s = new ListNode(666, head);//哨兵节点ListNode p1 = s;ListNode p2 = p1.next;while (p2 != null) {if (p2.val == val) {p1.next = p2.next;p2 = p2.next;} else {p1 = p1.next;p2 = p2.next;}}return s.next;}//代码优化版public ListNode removeElements2(ListNode head, int val) {ListNode s = new ListNode(666, head);//哨兵节点ListNode p1 = s;ListNode p2;while ((p2 = p1.next) != null) {if (p2.val == val) {p1.next = p2.next;} else {p1 = p1.next;}}return s.next;}

 //递归法 public ListNode removeElements(ListNode head, int val) {//如果头节点为空，则返回空if (head == null) {return null;}//如果头节点的值等于val，则返回移除头节点之后的链表if (head.val == val) {return removeElements(head.next, val);//否则，将头节点的下一个节点作为头节点，并递归调用removeElements函数，返回头节点} else {head.next = removeElements(head.next, val);return head;}}

  /**    非题解* Leetcode 很多链表题目用到的节点类*/
public class ListNode {public int val;public ListNode next;public ListNode(int val, ListNode next) {this.val = val;this.next = next;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder(64);sb.append("[");ListNode p = this;while (p != null) {sb.append(p.val);if (p.next != null) {sb.append(",");}p = p.next;}sb.append("]");return sb.toString();
//        return String.valueOf(this.val);}public static ListNode of(int... elements) {if (elements.length == 0) {return null;}ListNode p = null;for (int i = elements.length - 1; i >= 0; i--) {p = new ListNode(elements[i], p);}return p;}
}

给你一个链表，删除链表的倒数第 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

	//递归实现    public ListNode removeNthFromEnd(ListNode head, int n) {ListNode s = new ListNode(-1, head);//哨兵recursion(s, n);return s.next;}private int recursion(ListNode p, int n) {if (p == null) {return 0;}//nth:当前节点的下一个节点是倒数第几个节点int nth = recursion(p.next, n);if (nth == n) {p.next = p.next.next;}return nth + 1;}

	//双指针//删除倒数第n个节点public ListNode removeNthFromEnd2(ListNode head, int n) {ListNode s = new ListNode(-1, head);//哨兵ListNode p1 = s;ListNode p2 = s;//p2先移动n+1步  for (int i = 0; i <= n; i++) {p2 = p2.next;}//一起移动，直到p2为空  保持两个指针之间距离不变，当p2指向null时，p1所指的节点即为倒数第n个节点的上一个节点while (p2 != null) {p1 = p1.next;p2 = p2.next;}//删除倒数第n个节点p1.next = p1.next.next;return s.next;}

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

	//方法一：双指针public ListNode deleteDuplicates1(ListNode head) {//节点数<2if (head == null || head.next == null) {return head;}ListNode s = new ListNode(-1, head);//哨兵节点ListNode p1 = s;ListNode p2 = p1.next;while (p2 != null) {if (p1.val == p2.val) {p1.next = p2.next;p2 = p2.next;} else {p1 = p1.next;p2 = p2.next;}}return s.next;}//代码优化版public ListNode deleteDuplicates2(ListNode head) {//节点数<2if (head == null || head.next == null) {return head;}ListNode s = new ListNode(-1, head);//哨兵节点ListNode p1 = s;ListNode p2;while ((p2 = p1.next) != null) {if (p1.val == p2.val) {p1.next = p2.next;} else {p1 = p1.next;}}return s.next;}

这段代码是用于删除链表中的重复元素。有两个方法：deleteDuplicates1 和 deleteDuplicates2。

方法一：双指针

1. 首先创建一个哨兵节点 s，并将其指向链表的头节点 head。
2. 定义两个指针 p1 和 p2，分别指向哨兵节点 s 和 s.next（即链表的头节点）。
3. 当 p2 不为空时，进行以下操作：
   a. 如果 p1.val 和 p2.val 相等，说明当前节点是重复的，将 p1.next 指向 p2.next，即将当前节点的下一个节点从链表中删除。然后将 p2 指向下一个节点，继续遍历。
   b. 如果 p1.val 和 p2.val 不相等，说明当前节点不是重复的，将 p1 指向下一个节点，即 p1 = p1.next。然后将 p2 指向下一个节点，继续遍历。
4. 遍历结束后，返回哨兵节点 s 的下一个节点，即链表的头节点。

方法二：代码优化版

1. 与方法一相同，创建一个哨兵节点 s，并将其指向链表的头节点 head。
2. 定义一个指针 p1，指向哨兵节点 s。
3. 当 p2 不为空时，进行以下操作：
   a. 如果 p1.val 和 p2.val 相等，说明当前节点是重复的，将 p1.next 指向 p2.next，即将当前节点的下一个节点从链表中删除。
   b. 如果 p1.val 和 p2.val 不相等，说明当前节点不是重复的，将 p1 指向下一个节点，即 p1 = p1.next。然后将 p2 指向下一个节点，继续遍历。
4. 遍历结束后，返回哨兵节点 s 的下一个节点，即链表的头节点。

优化版与原始版的主要区别在于：原始版在找到重复节点时，会更新 p2 的值，而优化版在找到重复节点时，不会更新 p2 的值。这样可以减少不必要的计算，提高效率。

	//方法二：递归public ListNode deleteDuplicates(ListNode p) {if (p == null || p.next == null) {return p;}if(p.val == p.next.val){return deleteDuplicates(p.next);}else {p.next=deleteDuplicates(p.next);return p;}}

这段代码是用于删除链表中的重复元素。方法名 deleteDuplicates，输入参数为一个链表的头节点 p，返回值为删除重复元素后的链表的头节点。

方法二：递归

1. 如果链表为空或者链表只有一个节点，直接返回链表的头节点。
2. 如果当前节点的值等于下一个节点的值，说明当前节点是重复的，直接返回下一个节点去除重复元素后的链表的头节点。
3. 如果当前节点的值不等于下一个节点的值，说明当前节点不是重复的，将下一个节点去除重复元素后的链表的头节点接到当前节点的下一个节点，然后返回当前节点。

递归的核心思想是：将去除重复元素后的链表的头节点接到当前节点的下一个节点，然后返回当前节点。这样就可以实现从底层逐步向上去除重复元素。

给定一个已排序的链表的头 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
• 题目数据保证链表已经按升序 排列

	//方法一：递归public ListNode deleteDuplicates1(ListNode p) {if (p == null || p.next == null) {return p;}if (p.val == p.next.val) {ListNode p1 = p.next.next;while (p1 != null && p1.val == p.val) {p1 = p1.next;}return deleteDuplicates(p1);}else {p.next=deleteDuplicates(p.next);return p;}}

方法一：递归

1. 首先，判断输入的链表（p）是否为空或者只有一个节点，如果是，则直接返回该链表。
2. 如果当前节点的值（p.val）与下一个节点的值（p.next.val）相等，则需要删除重复的节点。具体操作如下： a. 创建一个指针p1，初始时指向当前节点的下一个节点。 b. 使用while循环，当p1不为空且p1的值与当前节点的值相等时，将p1指向下一个节点。 c. 最后，返回删除重复节点后的链表，即deleteDuplicates(p1)。
3. 如果当前节点的值与下一个节点的值不相等，则说明当前节点不需要删除，直接将当前节点的指针（p.next）指向下一个节点的递归结果，即deleteDuplicates(p.next)，然后返回当前节点。

总之，这个方法通过递归地处理链表中的每个节点，实现了删除重复元素的目的。

	//方法二：非递归，三指针public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}ListNode s = new ListNode(-1,head);//哨兵节点ListNode p1 = s;ListNode p2,p3;while ((p2 = p1.next)!=null&&(p3=p2.next)!=null){if(p2.val==p3.val){while ((p3 = p3.next)!=null&&p3.val==p2.val){}p1.next=p3;}else {p1 = p1.next;}}return s.next;}

这段代码是用于删除链表中的重复元素。它使用了非递归、三指针的方法。

1. 首先，创建一个哨兵节点（sentry node），将其指向链表的头节点（head）。
2. 然后，定义三个指针：p1、p2 和 p3。p1 指向哨兵节点，p2 指向 p1 的下一个节点，p3 指向 p2 的下一个节点。
3. 进入循环，当 p2 不为空且 p3 不为空时，执行以下操作： a. 比较 p2 和 p3 的值。如果它们相等，说明 p2 和 p3 指向的节点是重复的，需要删除。 i. 首先，通过循环找到下一个不等于 p2.val 的节点 p3。 ii. 然后，将 p1 的下一个节点指向 p3，即 p1.next = p3。 b. 如果 p2 和 p3 的值不相等，说明它们指向的节点不是重复的，将 p1 指向 p2 的下一个节点，即 p1 = p1.next。
4. 循环结束后，返回哨兵节点的下一个节点，即 s.next。

总之，这段代码通过非递归、三指针的方法实现了删除链表中的重复元素。

	//方法三：一次遍历public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}ListNode s = new ListNode(-1,head);//哨兵节点ListNode cur = s;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 s.next;}

这段代码是用于删除链表中重复的节点的。它使用了三种方法来解决这个问题，这里我们只解释一次遍历的方法。

1. 首先，创建一个哨兵节点（sentinel node）s，其值为-1，并将其next指针指向链表的头节点head。这样做的目的是为了方便处理链表的第一个节点可能也是重复的节点的情况。
2. 然后，定义一个指针cur，初始时指向哨兵节点s。
3. 进入循环，当cur.next不为空且cur.next.next不为空时，继续循环。
4. 在循环中，判断cur.next和cur.next.next的值是否相等。如果相等，说明这两个节点是重复的，需要删除。此时，我们定义一个变量x来存储重复的值，然后使用一个while循环来删除重复的节点。循环的条件是cur.next不为空，并且cur.next.val等于x。在循环中，将cur.next指向cur.next.next，从而删除重复的节点。
5. 如果cur.next和cur.next.next的值不相等，说明它们不是重复的节点，将cur指向cur.next，继续遍历下一个节点。
6. 最后，返回哨兵节点的下一个节点，即原始链表的头节点。

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 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 均按 非递减顺序 排列

//方法一：迭代public ListNode mergeTwoLists1(ListNode p1, ListNode p2) {ListNode s = new ListNode(-1, null);//新链表的哨兵节点ListNode p = s;while (p1 != null && p2 != null) {if (p1.val < p2.val) {p.next = p1;p1 = p1.next;} else {p.next = p2;p2 = p2.next;}p = p.next;}if (p1 != null) {p.next = p1;}if (p2 != null) {p.next = p2;}return s.next;}

这段代码是Java中用于合并两个有序链表的方法。给定的链表p1和p2都是有序的，因此我们可以通过比较它们的节点值来合并它们。

方法一：迭代

1. 首先，我们创建一个新的链表s，它的头节点是一个值为-1的节点，后面跟着一个空节点。这个新链表将用于存储合并后的节点值。
2. 然后，我们创建一个指针p，指向新链表的哨兵节点s。
3. 接下来，我们使用一个while循环来遍历p1和p2链表。在每次循环中，我们比较p1和p2节点的值。
4. 如果p1节点的值小于p2节点的值，我们将p节点的下一个指针指向p1节点，然后将p1节点向前移动一位。
5. 如果p2节点的值小于或等于p1节点的值，我们将p节点的下一个指针指向p2节点，然后将p2节点向前移动一位。
6. 最后，我们更新p指针，以便在下一轮循环中指向下一个节点。
7. 当p1或p2链表遍历完毕后，我们将另一个链表的剩余节点直接添加到新链表的末尾。
8. 最后，我们返回新链表的第一个节点，即s.next。

总之，这段代码实现了一个简单的迭代方法来合并两个有序链表。

//方法二：递归public ListNode mergeTwoLists(ListNode p1, ListNode p2) {if(p1==null){return p2;}if(p2==null){return p1;}if(p1.val<p2.val){p1.next=mergeTwoLists(p1.next,p2);return p1;}else {p2.next=mergeTwoLists(p1,p2.next);return p2;}}

这段代码是Java中用于合并两个有序链表的方法。给定的链表p1和p2都是有序的，因此我们可以通过比较它们的节点值来合并它们。

方法二：递归

1. 如果p1为空，则返回p2；如果p2为空，则返回p1。这是递归的终止条件。
2. 如果p1的值小于p2的值，我们将p1的下一个指针指向递归调用，该调用将p1的下一个节点与p2合并。然后返回p1。
3. 如果p2的值小于或等于p1的值，我们将p2的下一个指针指向递归调用，该调用将p1和p2的下一个节点合并。然后返回p2。

总之，这段代码实现了一个递归方法来合并两个有序链表。递归方法的主要优点是代码更简洁，但可能会导致额外的栈空间使用。

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

	/*如果两个链表合并可以解决，那么多链表合并就可以解决，分治思想，将多链表先分为两个链表*/	//分治思想：多路递归public ListNode mergeKLists(ListNode[] lists) {if (lists.length == 0) {return null;}ListNode node = split(lists, 0, lists.length - 1);return node;}//返回合并后的链表private ListNode split(ListNode[] lists, int i, int j) {if (i == j) {return lists[i];}int m = (i + j) >>> 1;ListNode left = split(lists, i, m);ListNode right = split(lists, m + 1, j);return mergeTowLists(left, right);}//合并两个链表 方法一：递归private ListNode mergeTowLists(ListNode p1, ListNode p2) {if (p1 == null) {return p2;}if (p2 == null) {return p1;}if (p1.val < p2.val) {p1.next = mergeTowLists(p1.next, p2);return p1;} else {p2.next = mergeTowLists(p1, p2.next);return p2;}}//合并两个链表 方法二：迭代private ListNode mergeTowLists2(ListNode p1, ListNode p2) {ListNode s = new ListNode(-1, null);ListNode p = s;while (p1 != null && p2 != null) {if (p1.val < p2.val) {p.next = p1;p1 = p1.next;} else {p.next = p2;p2 = p2.next;}p = p.next;}if (p1 != null) {p.next = p1;}if (p2 != null) {p.next = p2;}return s.next;}

这段代码是Java中用于合并K个有序链表的方法。给定的链表数组lists包含了K个链表，每个链表都是有序的。

分治思想：多路递归

1. 如果lists的长度为0，则返回null。
2. 调用split方法，该方法将链表数组lists分成两半，并返回合并后的链表。
3. split方法通过递归地将链表数组lists分成两半，然后将它们合并。

split方法：

1. 如果i等于j，则返回lists[i]。
2. 计算中间位置m，即将链表数组lists分成两半。
3. 递归地将链表数组lists分成两半，并将它们合并。

合并两个链表的方法一：递归

1. 如果p1为null，则返回p2；如果p2为null，则返回p1。这是递归的终止条件。
2. 如果p1的值小于p2的值，我们将p1的下一个指针指向递归调用，该调用将p1的下一个节点与p2合并。然后返回p1。
3. 如果p2的值小于或等于p1的值，我们将p2的下一个指针指向递归调用，该调用将p1和p2的下一个节点合并。然后返回p2。

合并两个链表的方法二：迭代

1. 创建一个新的链表s，其值为-1，并且next为null。
2. 创建一个指针p，初始值为s。
3. 当p1和p2都不为null时，比较它们的值。
4. 如果p1的值小于p2的值，则将p的下一个指针指向p1，并将p1的指针指向p1的下一个节点。
5. 如果p2的值小于或等于p1的值，则将p的下一个指针指向p2，并将p2的指针指向p2的下一个节点。
6. 将p指针移动到下一个节点。
7. 最后，如果p1不为null，则将p的下一个指针指向p1；如果p2不为null，则将p的下一个指针指向p2。
8. 返回s的下一个节点。

总之，这段代码实现了一个分治方法来合并K个有序链表。分治方法的主要优点是代码更简洁，但可能会导致额外的栈空间使用。

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

	//双指针：快慢指针public ListNode middleNode(ListNode head) {if(head.next==null){return head;}ListNode p1 = head;ListNode p2 = head;while (p2!=null||p2.next!=null){p1=p1.next;p2=p2.next.next;}return p1;}

这段代码是Java中用于找到链表的中间节点的的方法。给定的链表的头节点head。

双指针：快慢指针

1. 如果链表只有一个节点，则返回该节点。
2. 创建两个指针p1和p2，初始值都为头节点head。
3. 进入while循环，当p2不为null且p2的下一个节点不为null时，将p1移动到下一个节点，将p2移动到下一个节点的下一个节点。(p1走一步，p2走两步，当p2走到头，p1所在的节点就是中间节点)
4. 当p2为null或p2的下一个节点为null时，跳出循环。
5. 返回p1节点，即链表的中间节点。

总之，这段代码实现了一个简单的方法来找到链表的中间节点。这种方法通过使用快慢指针来遍历链表，当快指针到达链表尾部时，慢指针恰好到达链表的中间位置。

给你一个单链表的头节点 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) 空间复杂度解决此题？

	/*1.找到链表中间节点2.反转中间节点以后的链表3.将反转后的链表与原来的链表比较*/public boolean isPalindrome(ListNode head) {ListNode middle = this.middle(head);//1.找到链表中间节点ListNode newHead = this.reverse(middle);//2.反转中间节点以后的链表return this.compare(newHead, head);}  //返回中间节点：双指针private ListNode middle(ListNode p){ListNode p1 = p;ListNode p2 = p;while (p2!=null&&p2.next!=null){p1 = p1.next;p2 = p2.next.next;}return p1;}//反转链表private ListNode reverse(ListNode o1) {ListNode n1 = null;//反转后的新链表while (o1!=null){ListNode o2 = o1.next;o1.next = n1;n1 = o1;o1 = o2;}return n1;}//反转后的链表与原来链表做比较private boolean compare(ListNode newHead, ListNode head) {while (newHead!=null){if(newHead.val!=head.val){return false;}newHead = newHead.next;head = head.next;}return true;}

这段Java代码定义了一个名为isPalindrome的方法，该方法接受一个链表的头节点作为参数，并返回一个布尔值，表示该链表是否为回文链表。

以下是isPalindrome方法的详细步骤：

1. 找到链表中间节点：使用快慢指针法找到链表的中间节点。
2. 反转中间节点以后的链表：使用迭代法反转中间节点以后的链表。
3. 将反转后的链表与原来的链表比较：比较反转后的链表与原来的链表是否相等，相等则返回true，否则返回false。

以下是每个方法的详细说明：

1. 找到链表中间节点：

• 定义一个名为middle的方法，该方法接受一个链表节点p作为参数。
• 初始化两个指针p1和p2，都指向链表的头节点p。
• 当p2不为空且p2的下一个节点不为空时，将p1和p2分别向后移动一位。
• 最后返回p1，即链表的中间节点。

2. 反转中间节点以后的链表：

• 定义一个名为reverse的方法，该方法接受一个链表节点o1作为参数。
• 初始化一个空链表n1。
• 使用迭代法反转链表，具体实现如下：
  • 定义一个指向o1的指针o2，初始时o2为o1的下一个节点。
  • 将o1的下一个节点指向n1，即o1.next = n1。
  • 将n1指向o1，即n1 = o1。
  • 将o1指向o2，即o1 = o2。
  • 将o2向后移动一位，即o2 = o2.next。
• 当o2不为空时，重复上述步骤，直到链表反转完成。
• 最后返回n1，即反转后的新链表。

3. 将反转后的链表与原来的链表比较：

• 定义一个名为compare的方法，该方法接受两个链表节点newHead和head作为参数。
• 使用迭代法比较两个链表是否相等，具体实现如下：
  • 当newHead不为空时，比较newHead和head的值是否相等，如果不相等，返回false。
  • 将newHead和head分别向后移动一位，即newHead = newHead.next和head = head.next。
• 当newHead为空时，说明两个链表相等，返回true。

代码优化版：将查找中间节点和反转链表放在同一个循环中，在查找中链表的过程同时反转前半部分的链表

/*1.找到链表中间节点2.反转中间节点以后的链表3.将反转后的链表与原来的链表比较*/public boolean isPalindrome(ListNode head) {ListNode p1 = head;//慢指针ListNode p2 = head;//快指针ListNode n1 = null;//反转后新链表头结点ListNode o1 = head;//旧链表的头结点while (p2!=null&&p2.next!=null){//查找中间节点p1 = p1.next;p2 = p2.next.next;//反转前部分链表ListNode o2 = o1.next;//记录旧链表的头结点的下一个节点o1.next = n1;n1 = o1;o1 = o2;}//如果链表节点数为奇数，则从中间链表的下一个节点开始与反转链表进行比较if(p2!=null){p1 = p1.next;}while (n1 !=null){if(n1.val!= p1.val){return false;}n1 = n1.next;p1 = p1.next;}return true;}

这段代码定义了一个名为isPalindrome的方法，该方法接受一个链表的头节点作为参数。该方法的主要目的是检查给定的链表是否为回文链表。

以下是代码的详细解释：

1. 首先，定义了三个指针：p1、p2和n1。p1和p2用于找到链表的中间节点，而n1用于存储反转后新链表的头结点。

2. 然后，定义了两个指针：o1和o2。o1指向旧链表的头结点，而o2指向旧链表的头结点的下一个节点。

3. 在循环中，p1和p2指针分别向前移动两个节点。当p2的下一个节点不为空时，继续循环。

4. 在循环内部，首先记录旧链表的头结点的下一个节点o2。然后，将o1的下一个节点设置为n1，并将n1设置为o1。接着，将o1设置为o2，继续循环。

5. 当循环结束时，如果p2的下一个节点为空，说明链表长度为奇数，中间节点需要跳过。否则，说明链表长度为偶数，不需要跳过。

6. 接下来，使用n1指针遍历反转后的新链表，并与原始链表进行比较。如果两个链表的节点值不相等，则返回false，表示链表不是回文链表。如果遍历结束后没有找到不相等的节点，则返回true，表示链表是回文链表。