- Leetcode 206 反转链表
- Leetcode 92 反转链表 II
- Leetcode 83 删除排序链表中的重复元素
- Leetcode 82 删除排序链表中的重复元素 II
- Leetcode 86 分隔链表
- Leetcoe 328 奇偶链表
- Leetcode 2 两数相加
- Leetcode 445 两数相加 II
- Leetcode 203 移除链表元素
- Leetcode 21 合并两个有序链表
- Leetcode 24 两两交换链表中的结点
- Leetcode 25 K 个一组翻转链表
- Leetcode 237 删除链表中的节点
- Leetcode 61 旋转链表
- Leetcode 143 重排链表
- 剑指 offer 18 删除链表的结点
- 剑指 offer 06 从尾到头打印链表
- Leetcode 234 回文链表
Leetcode 206 反转链表
这是一道典型可以使用双指针解决的题目
首先假设有两个指针 p1 和 p2
首先 p1 指针指向了首结点，p2 指针指向了首结点的下一个结点
在 p2 不为 null 的情况下，我们需要的是不断将 p1 和 p2 后移，并保持一前一后的次序，然后将 p2.next 改为指向 p1。因此在这个过程中，为了保证能够在 p2.next 改变指向后依然能够找到下一个结点，我们需要一个临时指针来存储 p2.next 的地址，然后改变 p2.next 的指向，再移动 p1 和 p2 到新的结点上并循环操作
伪代码如下
while p2!=null:p1 -> 1 p2 -> 2p1.next = nulltmp = p2.next ( 3 )p2.next = p1p1 = p2p2 = tmp
这样就完成了一次两个结点之间的互换，只要循环此过程两两结点之间完成交换集合
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return null;
ListNode pre = head;
ListNode cur = head.next;
//断开第一个结点和第二个结点的连接，不然会造成回环
head.next = null;
while(cur != null){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
或者引入一个头结点，每次交换后重新连接头结点，这样就不用做回环的清除
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return null;
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
//pre 是永远的前驱
ListNode pre = dummyNode;
//cur 与 tmp 组成实际上的双指针
ListNode cur = dummyNode.next;
while(cur.next != null){
ListNode tmp = cur.next;
cur.next = tmp.next;
tmp.next = pre.next;
pre.next = tmp;
}
return dummyNode.next;
}
}
Leetcode 92 反转链表 II
这题与上一题的区别在于需要对 [m, n] 内的元素进行翻转，翻转算法同样可以使用快慢指针
但是这道题需要思考几个点
- 翻转以后如何与没有翻转的结点进行连接
- 如果头结点需要进行翻转，怎么办
对于第一个点，看一下这道题的示例
首先是一个 1->2->3->4->5 的链表，需要对 2->3->4 进行翻转。如果单从翻转以后来说，结构应该是这样的
1->2<-3<-4->5
现在需要做的是将 1 ( 即第 m 个结点的前一个结点 ) 指向翻转后链表的头部，将翻转后链表的尾部 2 指向头部 4 的下一个
由于我们使用了双指针，因此我们只需要多一次循环，就可以天然的将两个指针 ( p1 和 p2 ) 放到 4 和 5 上，这时我们只需要知道第 m 个结点的前一个结点 ( 假设为 p )，将 p.next = p1, p.next.next = p2，这时结构就变成了
1->4->3->2->5
满足了示例的要求
对于第二个点，如果我们想要对首结点进行翻转的话，那么我们就需要引入一个头结点，来完成对首结点的操作
这样看下来，代码就很简单了
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null || head.next == null) return head;
ListNode oneHead = new ListNode(-1);
oneHead.next = head;
//为了最后保证能对首结点进行同样的翻转操作，这里引入头结点
ListNode old = oneHead;
//指向第 m 个结点的前一个结点
for (int i = 1; i < m; i++) {
old = old.next;
}
//快慢指针翻转
ListNode p1 = null;
ListNode p2 = old.next;
for (int i = 0; i <= n-m; i++) {
ListNode tmp = p2.next;
p2.next = p1;
p1 = p2;
p2 = tmp;
}
//更改第 m 个结点的指向为 p2 当前指向的结点，也就是完成翻转后的第一个结点
old.next.next = p2;
//更改第 m-1 个结点的指向为 p1 当前指向的结点，也就是翻转后的第一个结点
//所以就完成了翻转后的头向尾连，尾向尾连的操作
old.next = p1;
return oneHead.next;
}
}
当然，因为我们引入了头结点，因此还可以写得更简单一些
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null || head.next == null) return head;
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
//永远指向 [m,n] 这个链表的前驱，在每次翻转结点后连接到新的头结点上
ListNode pre = dummyHead;
//指向第 m 个结点的前一个结点
for (int i = 1; i < m; i++) {
pre = pre.next;
}
//快慢指针翻转
ListNode cur = pre.next;
for (int i = 0; i < n-m; i++) {
ListNode tmp = cur.next;
cur.next = tmp.next;
tmp.next = pre.next;
pre.next = tmp;
}
return dummyHead.next;
}
}
Leetcode 83 删除排序链表中的重复元素
这道题目的关键点在于有序。首先想到思路的是，如果遇到相同大小的结点，就跳过，如果有多个相同大小的结点，则持续跳过，直到遇到一个大小不相同的结点，所以这个题也可以使用双指针
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null) return head;
ListNode pre = head;
ListNode cur = head.next;
while(cur != null){
//相同的就跳过，保证 cur 与 pre 指向的结点大小不同
if(pre.val == cur.val){
cur = cur.next;
}else{
//不同的就连接上，同时保证保留了第一个重复的
pre.next = cur;
pre = cur;
cur = cur.next;
}
}
//最后再连接一次，避免因为重复导致 cur 到 null 了，但是 pre 没来得及
//与 cur 连接
pre.next = cur;
return head;
}
}
Leetcode 82 删除排序链表中的重复元素 II
这题和 83 的区别在于，这道题需要删除所有出现了重复的元素，而不保留任何一个，所以来思考下如果我们继续沿用 83 题的解法能否得到一个正确的解
如果双指针遇到了大小不一样的结点，如果我们继续沿用上一题的方法，我们会将两个不同大小的结点进行连接，但是在这一题中，我们无法保证双指针中的快指针指向的结点与后面的结点不是大小相同的结点，而我们又要删除所有相同的结点，因此在这一题中并不能使用 83 的解法
因此，我们可以这样思考，假设有快慢指针分别是 cur 和 pre，当
- cur.val == cur.next.val 时，我们就将 cur 后移，直到找到一个和 cur.val 不同大小的结点，此时 cur 指向了最后一个重复结点
- 将 pre 与 cur 的下一个结点相连，这两个一定是不相同的结点
- 然后移动 cur 指针到下一个结点上
- 如果 cur.val != cur.next.val，同时移动快慢指针
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
//重复结点的前一个结点
ListNode pre = dummyNode;
ListNode cur = dummyNode.next;
while (cur != null && cur.next != null){
//当前结点与下个结点相同
if(cur.next.val == cur.val){
//循环直到最后一个当前重复的结点
while(cur.next != null && cur.val == cur.next.val){
cur = cur.next;
}
//将pre指向的不重复结点与cur的后驱相连，即去除了所有的重复结点
//但是 pre 不能移动，以保持快慢指针的前后顺序
pre.next = cur.next;
//移动 cur
cur = cur.next;
}else {
//如果不相同，则同时后移
pre = pre.next;
cur = cur.next;
}
}
return dummyNode.next;
}
}
Leetcode 86 分隔链表
很简单的一个思路，使用两个链表按照相对位置存储不同条件下的 ListNode，即可。但是注意，不能直接使用原来的链表中的结点，因为 Leetcode 会检查链表是否成环，即使在最后环解开了，Leetcode 也不会通过
class Solution {
public ListNode partition(ListNode head, int x) {
List<ListNode> list1 = new ArrayList<>();
List<ListNode> list2 = new ArrayList<>();
ListNode p = head;
while( p != null ){
if(p.val >= x){
list2.add(new ListNode(p.val));
}else{
list1.add(new ListNode(p.val));
}
p = p.next;
}
list1.addAll(list2);
ListNode re = new ListNode(0);
ListNode ptr = re;
for (ListNode listNode : list1) {
ptr.next = listNode;
ptr = ptr.next;
}
return re.next;
}
}
Leetcoe 328 奇偶链表
年轻人不讲码德
class Solution {
public ListNode oddEvenList(ListNode head) {
ArrayList<ListNode> list1 = new ArrayList<>();
ArrayList<ListNode> list2 = new ArrayList<>();
ListNode p = head;
int i = 1;
while( p != null ){
if( i%2 == 0 ){
list2.add(new ListNode(p.val));
}else {
list1.add(new ListNode(p.val));
}
i++;
p = p.next;
}
list1.addAll(list2);
ListNode headNode = new ListNode(0);
ListNode ptr = headNode;
for (ListNode listNode : list1) {
ptr.next = listNode;
ptr = ptr.next;
}
return headNode.next;
}
}
但是这题同样也可以很简单。。因为题目所定义的奇偶性是索引，所以可以通过双指针来遍历所有的奇偶结点，每一次循环都将两个奇结点 / 偶结点连接起来，最后形成两条链表，奇链表尾部连接偶链表首部即可
class Solution2{
public ListNode oddEvenList(ListNode head) {
//遍历所有奇结点，并连接，最后会指向最后一个奇结点，形成一个奇链表
ListNode ji = head;
//偶链表头结点，不能动
ListNode ou = head.next;
//遍历所有偶结点，并连接，最后指向最后一个偶结点，形成一个偶链表
ListNode tmp = ou;
while(ji.next != null && tmp.next != null){
//连接到下一个奇结点上
ji.next = tmp.next;
//连接到下一个偶结点上
tmp.next = tmp.next.next;
tmp = tmp.next;
ji = ji.next;
}
//最后奇链表尾结点连接到偶链表首结点
ji.next = ou;
return head;
}
}
Leetcode 2 两数相加
回想我第一次做这题还是在两年前。。。用的还是 C，玛德太痛苦了
现在再来看这题，其实就是两个链表从头加到尾，上个结点相加的值如果有进位，就进到下一个结点上相加，重复即可
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(-1);
ListNode tail = head;
//进位，初始为 0，每次循环时将两个数相加 / 10，赋值给 carry
//由于是每个位的相加，因此 carry 只有 0 和 1 两种可能
int carry = 0;
while(l1 != null || l2 != null){
//获得当前位上的值，如果没有就赋值为 0，保持位数一致方便计算
int v1 = l1!=null ? l1.val : 0;
int v2 = l2!=null ? l2.val : 0;
int sum = v1+v2+carry;
//尾连接,值为 sum 的个位，sum可能会大于等于10，因此%10取个位
tail.next = new ListNode(sum%10);
tail = tail.next;
//拿出进位数
carry = sum / 10;
//向后移动
if(l1 != null){
l1 = l1.next;
}
if(l2 != null){
l2 = l2.next;
}
}
//如果最后 carry 大于 0，再加一个结点
if(carry > 0){
tail.next = new ListNode(carry);
}
return head.next;
}
}
Leetcode 445 两数相加 II
这题和上一题很类似，如果忽略进阶要求的条件，最后再翻转一下最终的链表，那么就和上一题差不多了
但是这里要求的相加顺序是从低到高了，但是链表的顺序是相反的，因此需要思考有什么办法取出从低位到高位的所有数，然后一个个相加，再构造一个新的链表
栈就是个不错的选择，构造两个栈，将两个链表的所有结点的值入栈，再一个个出栈相加 ( 和上题类似的过程 )，然后使用头插法，还原结点的顺序
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
Stack<Integer> nodeStack1 = new Stack<>();
Stack<Integer> nodeStack2 = new Stack<>();
while (l1 != null){
nodeStack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null){
nodeStack2.push(l2.val);
l2 = l2.next;
}
ListNode head = null;
while (!nodeStack1.isEmpty() || !nodeStack2.isEmpty()){
//出栈，保证顺序从低到高
int v1 = !nodeStack1.isEmpty() ? nodeStack1.pop():0;
int v2 = !nodeStack2.isEmpty() ? nodeStack2.pop():0;
int sum = v1+v2+carry;
//头插法
ListNode tmp = new ListNode(sum%10);
tmp.next = head;
head = tmp;
//取进位值
carry = sum/10;
}
//如果还有进位值，添加结点
if(carry != 0){
ListNode tmp = new ListNode(carry);
tmp.next = head;
head = tmp;
}
return head;
}
}
Leetcode 203 移除链表元素
这个题可以说是 83 的简化版，因为给出了具体的值，遇到了相同大小结点直接跳过与后面一个结点相连即可
同时需要增加一个头结点，用来对首结点进行删除
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null) return null;
ListNode headNode = new ListNode(-1);
ListNode pTail = headNode;
headNode.next = head;
while (pTail.next != null){
if(pTail.next.val == val){
//跳过相同大小的结点，如果下个结点依然相同，则继续跳过
pTail.next = pTail.next.next;
}else{
//只有当结点不同了，才移动指针到不同的结点上，以继续向后搜索
pTail = pTail.next;
}
}
return headNode.next;
}
}
Leetcode 21 合并两个有序链表
这道题给了两个有序链表
- 我们从两个链表的首结点开始比较，谁比较小谁就作为首结点，与另一个首结点连接
- 使用一个指针指向当前已经组合了的链表的尾部，最终的目的是在尾部不断地添加
- 对于被更改了 next 的结点，我们同时需要移动位于该结点上的指针，因为被更改了指向的是作为当前最小的结点加入合并链表的，所以不需要再拿这个结点与另一个链表上的结点作比较
- 为了方便，我们可以设置一个头结点，这样就不用亲自操作结点，导致破坏了链表的连接指针
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//虚拟头结点，避免直接使用首结点导致链表结构被破坏
ListNode dummyNode = new ListNode(0);
ListNode tail = dummyNode;
while (l1 != null && l2 != null){
if(l1.val <= l2.val){
//尾部结点连接新的当前最小结点
tail.next = l1;
//成为新的尾结点
tail = l1;
//当前的最小结点已经于 l1 的链表上找到，移动 l1 指针继续比较
l1 = l1.next;
}else {
tail.next = l2;
tail = l2;
l2 = l2.next;
}
}
//连接没有遍历完的链表
tail.next = l1 == null ? l2:l1;
return dummyNode.next;
}
}
Leetcode 24 两两交换链表中的结点
首先，根据前面题目的规律，一旦涉及到要对首结点进行操作时 ( 移动，删除等 )，一般都会设置一个头结点来便于操作
再来分析一下这个题目，对于需要两两交换前后结点这个要求，我们可以使用双指针来操作这两个结点，但是需要注意的是，在两个结点交换位置后，他们的前驱结点需要重写进行指向，因此我们不妨再设置一个指针，永远指向两个待交换结点的前驱
最后，由于在交换后需要将双指针以及前驱指针移动到新的位置上，但是由于在交换过程中结点的先后顺序被颠倒了，因此为了方便操作，我们同样可以在两个待交换结点的后驱上设置一个指针，方便移动
有了上述思路，过程也就不难整理出来了
- 创建一个头结点
- 创建一个前驱指针，首先指向头结点
- 寻找交换两个结点的循环条件：只有当前驱指针的 .next 不为 null 并且 .next.next 不为 null 时，才会进行交换，否则是不交换的
- 创建三个指针 pre, cur, pTail：分别指向前后两个待交换结点，以及后驱结点
- 对两个结点的指向进行重新链接，需要让 cur 指针指向 pre，然后 pre 指向后驱 pTail，此时 cur 成了新的前结点，pre 就成为了新的后结点，然后让 pHead 指向 cur
- 移动 pHead 到新的前驱上，新的前驱就是 pre 指向的结点，现在该结点就是后结点，同时也是下两个待交换结点的前驱了
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
//指向需要交换的两个结点的之前一个结点
ListNode pHead = dummyNode;
//存在两个结点
while (pHead.next != null && pHead.next.next != null){
//需要交换的两个结点
ListNode pre = pHead.next;
ListNode cur = pHead.next.next;
//需要交换的两个结点的后驱
ListNode pTail = cur.next;
cur.next = pre;
pre.next = pTail;
pHead.next = cur;
pHead = pre;
}
return dummyNode.next;
}
}
对于上述过程，如果不太明白的话可以尝试画图，对于链表题目来说，本人觉得最重要的就是会画图
在上面所说的方法中，其实 pTail 是可以不用的，只需要调换一下两个待交换结点的重链接顺序即可
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
//指向需要交换的两个结点的之前一个结点
ListNode pHead = dummyNode;
//存在两个结点
while (pHead.next != null && pHead.next.next != null){
//需要交换的两个结点
ListNode pre = pHead.next;
ListNode cur = pHead.next.next;
//先将前一个结点链接到后驱上
pre.next = cur.next;
cur.next = pre;
pHead.next = cur;
pHead = pre;
}
return dummyNode.next;
}
}
Leetcode 25 K 个一组翻转链表
这题要求 k 个为一组翻转链表，而对于一个长度为 k 的链表，我们可以进行 k -1 次结点之间的交换
因此我们可以先求出链表的总长度，然后外层循环 length / k 次，内层循环 k-1 次即可翻转 k 个结点，这样就完成了 k 个链表的翻转
因此我们可以先用一个循环求出链表的长度，然后过程就如上所述，但是其中该如何进行交换是一个问题
首先我们这样来思考
- 我们首先需要一个头结点，用于在每次交换结点后能连接到新的首结点
- 每次内循环交换 k 个结点，即交换完成一组 k 链表后，将头结点的指针移动到 k 链表的末尾，因为上一个 k 链表的末尾是下个 k 链表的”头结点”
- 因为我们循环的是 length / k 次，所以对于剩余的结点会剩下来
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode countPtr = head;
int length = 0;
while (countPtr != null){
length++;
countPtr = countPtr.next;
}
//pre 其实在每次循环中指向的都是第 i 组 k 个结点组成的链表的前驱
ListNode pre = dummyNode;
//cur 其实在每次循环中是与 tmp 组成的快慢指针
ListNode cur = head;
for (int i = 0; i < length / k; i++) {
for (int j = 0; j < k - 1; j++) {
ListNode tmp = cur.next;
cur.next = tmp.next;
tmp.next = pre.next;
pre.next = tmp;
}
//移动 pre 到第 i 个 k 个结点组成的链表的最后一个结点上
//这个结点就是下一个 k 链表的前驱
pre = cur;
//移动 cur 到新的 k 链表的第一个结点上
cur = cur.next;
}
return dummyNode.next;
}
}
Leetcode 237 删除链表中的节点
如何让自己在世界上消失，但又不死？ —— 将自己完全变成另一个人，再杀了那个人就行了 ——摘自评论
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
Leetcode 61 旋转链表
单从示例中看，由于 5 移动到了 4 的前面，每一次都是将尾结点移动成为新的头结点
于是我结合了头插的方法，写出了下面这一版
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null) return head;
//本质就是不断把最后一个节点替换到前面来，类似于头插法
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode pHead = dummyNode;
for (int i = 0; i < k; i++) {
//每次循环找到当前的最后一个结点
ListNode tail = dummyNode.next;
//记录最后一个结点的前驱结点，用来断开连接
ListNode pre = dummyNode.next;
while (tail.next != null){
if(tail.next.next == null) pre = tail;
tail = tail.next;
}
tail.next = pHead.next;
pHead.next = tail;
pre.next = null;
}
return dummyNode.next;
}
}
啪，很快啊，超时了！！！！[1,2,3] 2000000000 ，这个测试用例我服了，耗子尾汁
其实一开始也不难看出 )，用循环链表也可以解决这问题
如果对循环链表足够熟悉，或者是画图看了的话，其实不难看出，所谓的移动 k 个位置，其实就是将循环链表的倒数第 k 个结点的前驱结点与第 k 个结点断开链接，然后这个前驱就作为了最终链表的尾部，而第 k 个结点就作为了新的头结点
因此问题就在于如何寻找倒数第 k 个结点的前驱，很简单的就是用链表长度 Length - k，但是由于这是个循环链表，因此题目给的 k 是可能超过链表长度的，所以如果想要找到其前驱，就需要循环 count = length -( k % length ) 次，就可以找到前驱
同时，由于我们需要返回新的头结点，以及将前驱指向 null，所以我们可以设置双指针，一个指针一开始在尾部，一个指针一开始在头部，由于是循环链表，当循环到 count 次时，前面的指针就指向了新的头结点，后面的指针就指向了新的尾结点
最后断开新的头尾的连接，返回新的头即可
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null) return head;
ListNode pHead = head;
ListNode tail = null;
int length = 1;
ListNode countPtr = head;
while (countPtr.next != null){
countPtr = countPtr.next;
length++;
}
//构成循环链表后
tail = countPtr;
tail.next = pHead;
//在构成循环链表后，移动 k 个位置就意味着可以将第 length - k 个结点
//的后驱断开，这样就完成了另一种意义上的移动
//由于 k 可能大于 length，因此循环链表的第 k 个结点的公式为 k % length
//所以循环次数就等于 count = k - (k % length)
int loop = length - (k % length);
for (int i = 0; i < loop; i++) {
pHead = pHead.next;
tail = tail.next;
}
tail.next = null;
return pHead;
}
}
Leetcode 143 重排链表
题目的需求很清楚，这里就不再解释了
仔细思考一下，我们的目的是将第 ( L , L ] 这些结点，插入到前面的结点之间，那么我们就可以
- 先找到中间结点的前驱 ( 快慢指针一次遍历或通过记录长度两次遍历 )，记录下其后驱，然后断开二者之间的连接，这样就形成了两个链表，我们的目的就是将后面链表的结点插入到前面的链表中。这里我们将后面的链表称为 after，前面的链表称为 before
- 由于插入顺序是 after 的逆序 ( 插入顺序是 after[L, L] )，因此我们可以先将 after 翻转
- 最后需要快慢指针，方便我们将翻转后的 after 中的结点插入到 before
- 在循环插入时，注意循环条件和其中的快指针的移动
- 在 after 链表没有被插入完成之前不能结束循环
- 在循环内，只有快指针不为 null 的时候才能移动快指针 ( 不理解的话可以画一个偶数长度的链表来看看 )
class Solution {
public void reorderList(ListNode head) {
if(head == null || head.next == null) return;
//快慢指针找到中点
ListNode quick = head;
ListNode slow = head;
while (quick.next != null && quick.next.next != null){
slow = slow.next;
quick = quick.next.next;
}
//翻转后半段链表，返回新链表的首结点
ListNode newMiddle = reverseAfterList(slow);
//见缝插针
ListNode pre = head;
ListNode cur = head.next;
while (newMiddle != null && pre != null){
ListNode tmp = newMiddle.next;
pre.next = newMiddle;
newMiddle.next = cur;
pre = cur;
//不为 null 才移动 cur，不然的话就说明可以直接从 afterList 中直接选取结点插入即可
if(cur != null){
cur = cur.next;
}
newMiddle = tmp;
}
}
private ListNode reverseAfterList(ListNode middle){
//找到后驱，即是后半段链表的头结点
ListNode afterSub = middle.next;
//断开前后连接
middle.next = null;
//翻转
ListNode afterDummyNode = new ListNode(0);
afterDummyNode.next = afterSub;
ListNode afterCur = afterDummyNode.next;
while (afterCur.next != null){
ListNode tmp = afterCur.next;
afterCur.next = tmp.next;
tmp.next = afterDummyNode.next;
afterDummyNode.next = tmp;
}
//返回翻转后的后半段链表的头结点
return afterDummyNode.next;
}
}
剑指 offer 18 删除链表的结点
很简单的题目，双指针即可，遇到等值结点跳过即可
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode pre = dummyNode;
ListNode cur = dummyNode.next;
while (cur != null){
if(cur.val == val){
pre.next = cur.next;
cur.next = null;
}
pre = pre.next;
cur = cur.next;
}
return dummyNode.next;
}
}
剑指 offer 06 从尾到头打印链表
很简单，翻转一次然后遍历存储即可
class Solution {
public int[] reversePrint(ListNode head) {
if(head == null) return new int[0];
LinkedList<Integer> list = new LinkedList<>();
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode pre = head;
//头插法翻转，并记录长度，以创建数组
int len = 0;
while (pre.next != null){
ListNode cur = pre.next;
pre.next = cur.next;
cur.next = dummyNode.next;
dummyNode.next = cur;
len++;
}
//遍历存储
int[] re = new int[len+1];
ListNode pHead = dummyNode.next;
for (int i = 0; i <= len; i++) {
re[i] = pHead.val;
pHead = pHead.next;
}
return re;
}
}
Leetcode 234 回文链表
<br />如果不考虑进阶要求的话，那可行解法就很多了，因此主要考虑下该如何满足进阶要求<br />其实仔细考虑一下，这题和重排链表很相似，如果我们能将后半部分的链表翻转过来的话，我们不需要插入前面的链表，只需要一个结点一个结点的比较即可，如果在比较完成之前有不相等的结点，那么就直接返回 false 即可；反之最后返回 true 即可
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
//找到中间结点
ListNode quick = head.next;
ListNode slow = head;
while (quick.next != null && quick.next.next != null){
quick = quick.next.next;
slow = slow.next;
}
ListNode mid = slow;
ListNode afterHead = reverseAfterList(mid);
ListNode beforeHead = head;
while (afterHead != null && beforeHead != null){
if(afterHead.val != beforeHead.val){
return false;
}else{
afterHead = afterHead.next;
beforeHead = beforeHead.next;
}
}
return true;
}
/**
* 翻转后半部分链表
* @param head：后半部分链表的前驱结点
* @return: 翻转后的头结点
*/
private ListNode reverseAfterList(ListNode head){
ListNode newHead = head.next;
head.next = null;
//头插法翻转
ListNode dummyNode = new ListNode(0);
dummyNode.next = newHead;
ListNode pre = dummyNode.next;
while (pre.next != null){
ListNode cur = pre.next;
pre.next = cur.next;
cur.next = dummyNode.next;
dummyNode.next = cur;
}
return dummyNode.next;
}
}
若有收获，就点个赞吧
0 人点赞
