力扣-数据结构-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());
}
}后言
上面是力扣数据结构相关，下一篇是其他的习题，希望有所帮助，一同进步，共勉！
