礼品册兑换 网站建设,网站备案需要那些资料,外链优化方法,绛县网站建设重排链表 解题思路#xff1a;通过观察链表可以发现#xff0c;把链表一分为二#xff0c;后半段链表反转#xff0c;然后两个链表穿插连接#xff0c;当链表的节点总数是奇数时#xff0c;要保证链表的前半段比后半段多一个节点。
关于把链表一分为二#xff0c;可以…重排链表 解题思路通过观察链表可以发现把链表一分为二后半段链表反转然后两个链表穿插连接当链表的节点总数是奇数时要保证链表的前半段比后半段多一个节点。
关于把链表一分为二可以采用定义快慢指针的做法快指针每次走两步慢指针每次走一步当快指针走到末尾时满指针也走到了中间节点。
重新定义反转函数reverseList() 代码如下:
class Solution {public void reorderList(ListNode head) {ListNode dummynew ListNode(0);//创建头节点dummy.nexthead;ListNode fastdummy;//定义快指针每次走两步ListNode slowdummy;//定义慢指针每次走一步while(fast!nullfast.next!null) {slowslow.next;fastfast.next;if(fast.next!null) {fastfast.next;}}//循环结束慢指针正好走到前半段链表的末尾//当链表节点总数是奇数时确保链表的前半段比后半段多一个节点ListNode tempslow.next;//后半段链表的开头节点slow.nextnull;//此时head代表链表的前半段temp代表链表的后半段//dummy代表有空头节点的head链表的前半段link(head,reverseList(temp),dummy);}private ListNode reverseList(ListNode head) {ListNode prenull;ListNode curhead;while(cur!null) {ListNode nextcur.next;cur.nextpre;//反转链表 第一步第一个节点的后面是null节点precur;curnext;}return pre;}public void link(ListNode node1,ListNode node2,ListNode head) {ListNode prehead;//带头结点while(node1!nullnode2!null) {ListNode tempnode1.next;pre.nextnode1;node1.nextnode2;prenode2;node1temp;node2node2.next;}if(node1!null) {pre.nextnode1;} }
}第二种方法使用双端队列deque deque做队列使用时继承了Queue的接口所以插入元素操作可以使用Queue的用法offer()或者相当于deque的从队尾插入元素offerLast()
offerLast(): 向队尾插入元素如果插入成功返回true否则返回false
removeFirst(): 返回并移除队头元素如果该元素是null则发生NoSuchElementException
removeLast(): 返回并移除队尾元素如果该元素是null则发生NoSuchElementException代码如下
class Solution {public void reorderList(ListNode head) {DequeListNode dequenew LinkedList();ListNode curhead;while(cur!null) {deque.offer(cur);//双端队列入队curcur.next;}curhead;//指针又回到头节点for(int i0;!deque.isEmpty();i,curcur.next,cur.nextnull) {cur.nexti%20?deque.removeFirst():deque.removeLast();}
}
}Deque的用法 1.Deque的介绍
public interface DequeE extends QueueEDeque是一个双端队列接口继承来自Queue接口 Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque但是一般常用LinkedList实现接口。 1一般场景 LinkedList 大小可变的链表双端队列允许元素为null ArrayDeque 大小可变的数组双端队列不允许null 2并发场景 LinkedBlockingDeque如果队列为空时获取操作将会阻塞知道有元素添加 定义的函数 Deque实现了双向队列队列和栈的功能 普通队列
DequeE dequenew LinkedList()双端队列
DequeE dequenew LinkedList()堆栈
DequeE dequenew LinkedList()
