给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
需要注意的是,不能只是单纯地改变结点内部的值,而是需要实际的进行节点交换
这个代码在Leetcode上提交显示超出时间限制
//两两交换链表中的结点
public ListNode swapPairs(ListNode head){
ListNode dummyHead=new ListNode(0);//设置虚拟头结点
dummyHead.next=head;
ListNode curNode=dummyHead;
//假设链表是cur->1->2->3->4->5
ListNode temp= curNode.next;//临时结点,保存1这个节点
ListNode temp1=curNode.next.next.next;//临时结点,保存3这个节点
while (curNode.next!=null && curNode.next.next!=null){
//将2与1调换
//步骤一:
curNode.next=curNode.next.next;//cur->2
//步骤二:
curNode.next.next=temp;//cur->2->1
curNode.next.next.next=temp1;//cur->2->1->3
curNode=curNode.next.next;//cur移动两位,准备下一轮交换,此时cur指向3这个节点
}
return dummyHead.next;
}
//两两交换链表中的结点------优化
public ListNode swapPairs1(ListNode head){
ListNode dummyHead=new ListNode(0);//设置虚拟头结点
dummyHead.next=head;
ListNode curNode=dummyHead;
//假设链表是cur->1->2->3->4->5
ListNode temp;//保存两个结点后面的结点,也就是保存3这个节点
ListNode firstNode;//保存两个节点中的第一个结点,也就是保存1这个节点
ListNode secondNode;//保存两个节点中的第二个 结点,也就是2这个节点
while (curNode.next!=null && curNode.next.next!=null){
temp=curNode.next.next.next;//保存两个结点后面的结点,也就是保存3这个节点
firstNode=curNode.next;//保存两个节点中的第一个结点,也就是保存1这个节点
secondNode=curNode.next.next;//保存两个节点中的第二个 结点,也就是2这个节点
//将2与1调换
//步骤一:
curNode.next=secondNode;//cur->2
//步骤二:
secondNode.next=firstNode;//cur->2->1
firstNode.next=temp;//cur->2->1->3
curNode=firstNode;//cur移动两位,准备下一轮交换,此时cur指向3这个节点
}
return dummyHead.next;
}
思路:
例如:n=2,删除倒数第2个,也就是删除元素3
public ListNode removeNthFromEnd(ListNode head,int n){
//设置虚拟头结点
ListNode dummyHead=new ListNode(0);
dummyHead.next=head;
//快慢指针
ListNode fastIndex=dummyHead;
ListNode slowIndex=dummyHead;
//只要快慢指针相差n个结点即可 先让快指针向前移动n步
for (int i=0;i<n;i++){
fastIndex=fastIndex.next;
}
//快指针向前移动n步后,快慢指针同时移动
while (fastIndex.next!=null){
fastIndex=fastIndex.next;
slowIndex=slowIndex.next;
}
//此时慢指针的位置就是待删除元素的前一个位置
slowIndex.next=slowIndex.next.next;//删除操作
return dummyHead.next;
}
/**
* 环形链表II
* 返回链表开始入环的第一个节点
*/
public ListNode detectCycle(ListNode head){
ListNode slow=head;
ListNode fast=head;
while (fast!=null && fast.next!=null){
slow=slow.next;//slow走一步
fast=fast.next.next;//fast走两步
if (fast==slow){//有环
ListNode index1=fast;
ListNode index2=head;
//两个指针,从头结点和相遇结点,各走一步,直到相遇,相遇点即为环入口
while (index1 != index2){
index1=index1.next;
index2=index2.next;
}
return index1;
}
}
return null;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁