? ? 单链表的实现 简单介绍了单链表的增删查改，这一篇介绍单链表的另一些比较常见的操作，比如单链表的反转、求单链表的中间节点、合并两个升序的单链表、判断一个链表是不是回文结构等。这些操作在力扣上面也有对应的题目。下面这些题目来源均为力扣。
首先定义好这个单链表。所有的操作都是基于这个单链表而来。
class ListNode {
int val;
ListNode next;
public ListNode() {};
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}1、反转单链表
206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)
https://leetcode-cn.com/problems/reverse-linked-list/description/给你单链表的头节点??head? ，请你反转链表，并返回反转后的链表。
示例：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
输入：head = [1,2] 输出：[2,1]
输入：head = [] 输出：[]
public ListNode reverseList(ListNode head) {
//输入你的代码
}题解：
这个操作还算是简单的。在整个过程中，需要拿出纸笔来画一画，过程就会明了。
? ? 定义head（ListNode类型）是头节点，整个链表通过它来找到，不能动。定义cur（ListNode类型）表示当前节点。就拿链表中值为1和2的节点来说。要反转这俩个链表，只需要让值为2的节点的next引用指向值为1这个节点。同时，第一个节点是头节点，把它的next域置为空。从图上，最直观的就是让cur.next直接指向head，就完成了链表的反转。同时，让cur走向下一个节点。
? ? 但问题是，第二个节点cur指向了第一个节点，不在指向第三个节点。如何找到第三个节点？要临时保存第三个节点，才能找到它。也就是说，整个过程，需要三个节点变量。
? ? 如图，定义了cur、prev和curNext。其中，cur表示当前节点，curNext表示当前节点的下一个，prev表示前一个节点。改变了cur.next的引用，指向prev后，先让prev移动到cur，在让cur移动到curNext。
? ? 结束的条件是当cur指向null的时候，表示最后一个链表也被反转了。特殊的，当链表是空链表的时候，直接返回null；当链表只有一个节点的时候，直接返回这个节点。
public ListNode reverseList(ListNode head) {
//链表为空
if (head == null) {
return null;
}
//链表只有一个节点
if (head.next == null) {
return head;
}
ListNode prev = head;
ListNode cur = head.next;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = prev;
prev = cur;
cur = curNext;
}
//处理第一个节点，指向置为null
head.next = null;
//prev所处位置是新头节点位置
head = prev;
return head;
}2、求单链表中间节点
给定一个头结点为?head?的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
public ListNode middleNode(ListNode head) {
//输入你的代码
}题解：
? ? 使用快慢指针。定义fast和slow。其中，快的指针fast一次走两步，慢的指针slow一次走一步。当快的指针走到尾结点的时候，慢的指针正好走到了整个链表的中间节点。
? ? 这是链表节点为奇数的时候，结束的条件是fast.next为null。如果链表节点是偶数的时候，情况有点不一样。
链表节点是偶数的时候，fast直接为空。
? ? 特殊的，当链表是空的时候，直接返回null；当链表只有一个节点的时候，返回这个节点。代码如下：
public ListNode middleNode(ListNode head) {
//空链表
if (head == null) {
return null;
}
//链表只有一个节点
if (head.next == null) {
return head;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}3、合并两个有序（升序）链表
21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/merge-two-sorted-lists/description/? ? 将两个升序链表合并为一个新的?升序?链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。?
示例：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
输入：l1 = [], l2 = [] 输出：[]
输入：l1 = [], l2 = [0] 输出：[0]
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//输入你的代码
}题解：
? ? 本题在做的时候，首先需要一个头节点来串起来整个的链表。要先判断两个链表的头节点中，哪一个能够作为整个有序链表的头节点。把这个头节点单独拿出来，比如，将值为-1的节点置为头节点，这样就可以减少代码量的同时，方便我们解题。这样的头节点只是为了解题的需要，称为哨兵节点。
? ? 返回的节点从head.next开始，它才是整个链表的真正的头节点。本题可以使用哨兵节点，也可以不使用。现在来使用哨兵节点解决这个问题。
? ? 要升序进行链表的排序，就需要比较list1.val和list2.val值的大小。这是第一次比较。如果list1.val小于list2.val的话，就让哨兵节点指向list1，否则list2。完成后，需要让小的list1开始动到下一个节点，在进行比较。在整个比较的过程中，head是不能动的，设置cur来完成。
? ? 当其中一个链表被遍历完成的时候，另一个链表余下的部分就直接连接到后面。特殊的，当两个链表中有一个是空，就返回另一个链表的头节点。
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//两个链表中有一个是空
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
//哨兵节点
ListNode newHead = new ListNode(-1);
ListNode cur = newHead;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
cur.next =list1;
list1 = list1.next;
tmp = cur.next;
} else {
cur.next = list2;
list2 = list2.next;
tmp = cur.next;
}
}
//当有一个遍历完而另一个没有遍历完
if (list1 != null) {
cur.next = list1;
} else {
cur.next = list2;
}
return newHead.next;
}4、回文链表
剑指 Offer II 027. 回文链表 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/aMhZSa/给定一个链表的?头节点?head?，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
示例：
输入: head = [1,2,3,3,2,1] 输出: true
输入: head = [1,2] 输出: false
public boolean isPalindrome(ListNode head) {
//输入你的代码
}题解：
? ? 我们以前肯定做过数组的回文结构。做数组的回文结构的时候，定义两个指针，一个从0下标开始，一个从数组最后一个元素开始，两个向中间靠近，在这个期间，如果有值不相等的时候，说明不是回文结构，走到了中间，说明这个数组就是回文结构。
? ? 这个思路放在链表上如何实现呢，定义两个指针，一个从头节点开始，另一个从尾结点开始。当两个指针往中间节点走的过程，如果有一对节点的值不相等，就不是回文结构，到了中间位置，说明就是回文结构。那么，从尾结点如何走到中间节点呢，要中间节点到尾节点的链表进行反转。这道题是综合了链表反转和求链表的中间节点。找到链表的中间节点后，反转后半部分的节点，在进行判断。
如果这个链表的节点是奇数个，那么到中间的时候，就不是fast.next=slow,而是fast=slow了。
? ? 特殊的，当链表是空的时候，假设是false，具体的结果看出题的判断；当链表只有一个节点的时候，一个节点也是回文结构，返回true。
public boolean isPalindrome(ListNode head) {
if (head == null) {
return false;
}
if (head.next == null) {
return true;
}
ListNode fast = head;
ListNode slow = head;
//链表寻找中间节点
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//链表反转
ListNode cur = slow.next;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//判断回文结构
fast = head;
while (fast != slow) {
if (fast.val != slow.val) {
return false;
}
if (fast.next == slow) {
return true;
}
fast = fast.next;
slow = slow.next;
}
return true;
}
