我要评论
五道单链表中等难度题型
1. 剑指 offer ii 021. 删除链表的倒数第 n 个结点
题目描述：
三种解法：
第一种解法（单指针）：
代码如下：
class solution {
public listnode removenthfromend(listnode head, int n) {
listnode dummy = new listnode(0, head);//设置哨兵位
int length = getlength(head);//求出链表长度
listnode cur = dummy;//用cur去遍历
//遍历l-n+1次就是要删除结点的前驱结点
for (int i = 1; i < length - n + 1; ++i) {
cur = cur.next;
}
//前驱结点的next指向要删除结点的后一个结点
cur.next = cur.next.next;
return dummy.next;
}
//求出链表长度
public int getlength(listnode head) {
int length = 0;
while (head != null) {
++length;
head = head.next;
}
return length;
}
}
作者总结：
复杂度分析：
第二种解法(栈)：
实现思路：
具体实现：
如图：
代码如下：
class solution {
public listnode removenthfromend(listnode head, int n) {
listnode dummy = new listnode(0, head);//创建哨兵位
deque<listnode> stack = new linkedlist<listnode>();//创建一个栈
listnode cur = dummy;//cur代替哨兵位遍历
while (cur != null) {
//依次放入
stack.push(cur);
cur = cur.next;
}
//弹出倒数n个结点
for (int i = 0; i < n; ++i) {
stack.pop();
}
//当前栈顶就是要删除结点的前驱结点
listnode prev = stack.peek();
//
prev.next = prev.next.next;
return dummy.next;
}
}
作者总结：
复杂度分析：
第三种解法（双指针）：
解题思路：
具体实现：
如图：
代码如下：
class solution {
public listnode removenthfromend(listnode head, int n) {
//判断是否为空
if(head==null) {
return head;
}
//创建一个哨兵位
listnode newhead=new listnode(0);
//哨兵位的next指向head
newhead.next=head;
//将cur和prev同时指向newhead
listnode cur=newhead;
listnode prev=newhead;
//快指针先走n+1步（也可以快指针总head走，走n步就可以，核心思路就是慢指针要和快指针之间的距离差1）
for(int i=0;i<n+1;i++) {
cur=cur.next;
}
//两个指针一起走
while(cur!=null) {
cur=cur.next;
prev=prev.next;
}
//最后删除倒数第n个结点
prev.next=prev.next.next;
//返回newhead的next
return newhead.next;
}
}
作者总结:
复杂度分析：
2. 删除排序链表中的重复元素 ii（重点）
题目描述：
需要考虑的事项：
一种普通状态：
两种特殊状态：
普通状态
解题思路：
如图：
最后运行结果：
特殊状态（头结点重复时）
运行结果：
特殊状态（删除尾结点时）
解决之后运行结果：
具体代码如下：
class solution {
public listnode deleteduplicates(listnode head) {
if(head==null||head.next==null) {
return head;
}
listnode prev=null;
listnode cur=head;
listnode curnext=cur.next;
while(curnext!=null) {
//当他们的值不同时，集体后移，注意顺序
if(cur.val!=curnext.val) {
prev=cur;
cur=curnext;
curnext=curnext.next;
} else {
//当他们的值相同时，并且curnext不为空，进入循环
//注意要将curnext！=null的判断条件写在左边
//逻辑运算&&，先判断左边，如果左边为真才判断右边，
//当你的curnext!=null写在右边时，
//他会先进行curnext.val的操作，此时你的curnext已经为空
//再去访问就会发出空指针异常
while(curnext!=null&&cur.val==curnext.val) {
curnext=curnext.next;
}
//判断prev是否为空，如果为空就是头删
if(prev!=null) {
//不为空将prev的next指向curnext
prev.next=curnext;
} else {
//为空则头节点变成curnext
head=curnext;
}
//后续过程不变
cur=curnext;
//判断curnext是否为空，如果为空则不进行该操作
if(curnext!=null)
curnext=curnext.next;
}
}
return head;
}
}
作者总结：
复杂度分析：
3. 删除链表中的节点
题目描述：
解题思路:
如下图：
代码如下：
class solution {
public void deletenode(listnode node) {
node.val=node.next.val;//替换为下一个结点的val
node.next=node.next.next;//替换为下一个结点的next
}
}
总结：
复杂度分析：
4. 重排链表
题目描述：
大概意思就是：
解题思路：
思路一：
具体实现：
代码如下：
class solution {
public void reorderlist(listnode head) {
if(head==null||head.next==null) {
return;
}
//利用顺序表存储，然后按指定位置
//我这里没有直接使用库的顺序表，
listnode [] array=new listnode[50000];
listnode cur=head;//
int i=0;
//从0下标存入
while(cur!=null) {
array[i]=cur;
cur=cur.next;
i++;
}
//最后i是元素个数
listnode newhead=new listnode(0);
listnode newprev=newhead;
int a=0;//a是下标
int b=i-1;//b也是下标,i是元素个数，元素个数-1就是最后一个元素的下标
int count=1;//根据奇偶判断读取哪个下标的元素
//最后i+1就是链表的结点个数+1，
//count是从1开始的，所以当count=i+1时，就代表读取完了所有结点
while(count!=i+1) {
//如果是奇数，就顺序读取
if(count%2!=0) {
newprev.next=array[a];
newprev=newprev.next;
a++;//
} else{
//如果是偶数就逆序读取
newprev.next=array[b];
newprev=newprev.next;
b--;
}
count++;
}
//将左后一个结点呢next置为kong,防止循环
newprev.next=null;
//将头节点改为newhead的next
head=newhead.next;
}
}
复杂度分析：
思路二（寻找链表中点 + 链表逆序 + 合并链表）
思路二：
如图：
注意：
具体步骤：
代码如下（注意注释）
class solution {
public void reorderlist(listnode head) {
if(head==null||head.next==null) {
return;
}
//找到中间结点
listnode prev=head;//慢指针
listnode cur=head;//快指针
while(cur!=null&&cur.next!=null) {
cur=cur.next.next;
prev=prev.next;
}
//逆序单链表
cur=reverse(prev);
prev=head;//prev从头遍历
listnode newhead=new listnode(0);
listnode newprev=newhead;
int i=1;//来判断调用谁的结点
while(true) {
if(i%2!=0) {
newprev.next=prev;//衔接该结点
//当两个结点相等时退出循环
if(prev==cur) {
//并将newprev置为下一个结点
newprev=newprev.next;
break;
}
prev=prev.next;//prev指向下一个结点
} else {
newprev.next=cur;//衔接该结点
//当两个结点相等时退出循环
if(prev==cur) {
//并将newprev置为下一个结点
newprev=newprev.next;
break;
}
cur=cur.next;//cur指向下一个结点
}
i++;
newprev=newprev.next;//置为下一个结点
}
newprev.next=null;//将尾结点的next置为null,防止循环
}
//逆置链表函数
public listnode reverse(listnode head) {
listnode prev=null;
listnode cur=head;
while(cur!=null) {
listnode curnext=cur.next;
cur.next=prev;
prev=cur;
cur=curnext;
}
return prev;
}
作者总结：
复杂度分析：
5. 剑指 offer ii 077. 链表排序（重点！）
题目描述：
解题思路：
如图：
listnode cur=head.next;//后续链表的头指针
listnode newhead=head;//当前有序链表的头指针
newhead.next=null;//与后续链表断开联系
listnode prev=newhead;//有序链表向后遍历指针的前驱指针
listnode prevnext=newhead.next;//用于有序链表向后遍历的指
针
listnode last=newhead;//尾结点
listnode curnext=cur.next;//用于找回后续链表的指针
具体实现:
插入过程：
（有小瑕疵，cur跟尾结点比较的过程忽略了，直接按顺序对比去了，但是大体思路是这样）
代码如下：
class solution {
public static listnode sortlist(listnode head) {
if (head == null || head.next == null) {
return head;
}
listnode cur=head.next;//后续链表的头节点
listnode newhead=head;//当前有序链表的头节点
newhead.next=null;//与后续链表断开联系
listnode prevnext=newhead.next;//有序链表向后遍历的结点
listnode prev=newhead;//有序链表向后遍历结点的前驱结点
listnode last=newhead;//尾结点
while(cur!=null) {
//头插
listnode curnext =cur.next;
if(newhead.val>=cur.val) {
cur.next=newhead;
newhead=cur;
} else if(last.val<cur.val) {
//尾插
last.next=cur;
last=cur;
last.next=null;
} else {//中间插入
//找到大于等于cur.val的结点
while(cur.val>prevnext.val) {
//prev一直保存prevnext的前一个结点
prev=prevnext;
//prevnext置为它的下一个结点
prevnext=prevnext.next;
}
//将cur插入prev和prevnext之间
prev.next=cur;
cur.next=prevnext;
}
//重置prev
prev=newhead;
//重置prevnext
prevnext=prev.next;
//重置cur
cur=curnext;
}
//返回新头节点
return newhead;
}
}
作者总结：
复杂度分析：
发表评论