力扣-数据结构-3【算法学习day.74】

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.反转偶数长度组的节点

题目链接:2074. 反转偶数长度组的节点 - 力扣（LeetCode）

题面:

分析:用数组存值的同时再开一个falg数组存一下每个节点所属的组，对于非最后一组来说，如果是偶数组，那么该组个数也是偶数个，进行翻转，对于最后一组，提前统计最后一组的个数，如果为偶数，就进行反转，反转过程中使用虚拟头节点更方便

/*** 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 reverseEvenLengthGroups(ListNode head) {int[] arr = new int[100005];int[] flag = new int[100005];int inz = 1;int index = 1;int count = 1;for(ListNode i = head;i!=null;i = i.next){flag[index] = inz;arr[index++] = i.val;if(count==inz){count = 1;inz++;}else{count++;}}int blag = flag[index-1];int lastcount = 1;for(int i = index-2;i>=1&&flag[i]==blag;i--)lastcount++;ListNode fhead = new ListNode(-1);fhead.next = head;ListNode pre = fhead;index = 1;int left = 3;boolean firstin = true;// System.out.println(blag+"         "+lastcount);for(ListNode i = head;i!=null;i = i.next){if(flag[index]!=flag[index-1]){firstin = true;}if((flag[index]%2==0&&flag[index]!=blag)||(flag[index]==blag&&lastcount%2==0)){if(firstin){if(flag[index]==blag){left = index+lastcount-1;}else{left = index+flag[index]-1;}firstin = false;}ListNode node = new ListNode(arr[left--]);pre.next = node;pre = node;}else{pre.next = i;pre = i;}index++;}return fhead.next;}
}

2.旋转链表

题目链接:61. 旋转链表 - 力扣（LeetCode）

题面:

分析:可以通过计算出向右移动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)return null;int count = 0;for(ListNode i = head;i!=null;i=i.next){count++;}int flag = k%count;int bindex = count-flag+1;int index = 1;ListNode fhead = new ListNode();fhead.next = head;ListNode pre = fhead;ListNode ans = null;for(ListNode i = head;i!=null;i =i.next){if(index==bindex){ans = i;ListNode node = null;pre.next = node;}if(index==count){i.next = fhead.next;}pre = i;index++;}return ans;}
}

3.交换链表中的节点

题目链接: 1721. 交换链表中的节点 - 力扣（LeetCode）

题面:

分析:找到正数和倒数两个节点的索引位置，并存一下值，这里用递归比较方便，然后遍历链表修改值

代码:

/*** 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 {ListNode head;int k;int zval = -1;int rval = -1;int r = 0;public ListNode swapNodes(ListNode head, int k) {this.head = head;this.k = k;recursion(head,1);int index = 1;for(ListNode i = head;i!=null;i=i.next){if(index==k){i.val = rval;}else if(index==r){i.val = zval;}index++;}return head;}public int recursion(ListNode node,int z){if(node==null)return 1;if(z==k){zval = node.val;}int r2 = recursion(node.next,z+1);if(r2==k){rval = node.val;r = z;}return r2+1;}
}

4.链表的中间节点

题目链接:876. 链表的中间结点 - 力扣（LeetCode）

题面:

分析:可以用递归分别统计节点的个数和答案节点的索引，在回溯过程中如果回溯到答案节点，返回

代码:

/*** 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 {int flag = -1;ListNode ans = null;public ListNode middleNode(ListNode head) {recursion(head,1);return ans;}public void recursion(ListNode node,int z){if(node==null){flag =(z-1)/2+1;return;}recursion(node.next,z+1);if(z==flag){ans = node;return;}}
}

5.删除链表的中间节点

题目链接: 2095. 删除链表的中间节点 - 力扣（LeetCode）

题面:

分析:快慢指针，慢指针每次走一步，快指针每次走两步，当快指针指向的位置是最后一个节点或者是null，此时慢指针更好指向中间节点，然后正常删除就行

代码:

/*** 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 deleteMiddle(ListNode head) {if(head==null||head.next==null)return null;ListNode pre = head;for(ListNode i = head ,j=head;i!=null;i=i.next){if(j==null||j.next==null){ListNode node = i.next;pre.next = node;break;}      j=j.next.next;pre = i;}return head;}
}

6.回文链表

题目链接:234. 回文链表 - 力扣（LeetCode）

题面:

分析:使用StringBuilder的reverse方法

代码:

/*** 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) {StringBuilder sb = new StringBuilder();for(ListNode i = head;i!=null;i=i.next){sb.append(i.val+"");}// System.out.println(sb.reverse().toString());// System.out.println(sb.toString());return sb.toString().equals(sb.reverse().toString());}
}