刷题25-重排链表

重排链表


解题思路：通过观察链表可以发现，把链表一分为二，后半段链表反转，然后两个链表穿插连接，当链表的节点总数是奇数时，要保证链表的前半段比后半段多一个节点。

关于把链表一分为二，可以采用定义快慢指针的做法，快指针每次走两步，慢指针每次走一步，当快指针走到末尾时，满指针也走到了中间节点。

重新定义反转函数reverseList()
代码如下:

class Solution {public void reorderList(ListNode head) {ListNode dummy=new ListNode(0);//创建头节点dummy.next=head;ListNode fast=dummy;//定义快指针，每次走两步ListNode slow=dummy;//定义慢指针，每次走一步while(fast!=null&&fast.next!=null) {slow=slow.next;fast=fast.next;if(fast.next!=null) {fast=fast.next;}}//循环结束，慢指针正好走到前半段链表的末尾//当链表节点总数是奇数时，确保链表的前半段比后半段多一个节点ListNode temp=slow.next;//后半段链表的开头节点slow.next=null;//此时head代表链表的前半段，temp代表链表的后半段//dummy代表有空头节点的head链表的前半段link(head,reverseList(temp),dummy);}private ListNode reverseList(ListNode head) {ListNode pre=null;ListNode cur=head;while(cur!=null) {ListNode next=cur.next;cur.next=pre;//反转链表 第一步，第一个节点的后面是null节点pre=cur;cur=next;}return pre;}public void link(ListNode node1,ListNode node2,ListNode head) {ListNode pre=head;//带头结点while(node1!=null&&node2!=null) {ListNode temp=node1.next;pre.next=node1;node1.next=node2;pre=node2;node1=temp;node2=node2.next;}if(node1!=null) {pre.next=node1;}	}
}

第二种方法：使用双端队列deque
deque做队列使用时，继承了Queue的接口，所以插入元素操作可以使用Queue的用法offer()或者相当于deque的从队尾插入元素offerLast()

offerLast(): 向队尾插入元素，如果插入成功返回true，否则返回false
removeFirst(): 返回并移除队头元素，如果该元素是null，则发生NoSuchElementException
removeLast(): 返回并移除队尾元素，如果该元素是null，则发生NoSuchElementException

代码如下：

class Solution {public void reorderList(ListNode head) {Deque<ListNode> deque=new LinkedList<>();ListNode cur=head;while(cur!=null) {deque.offer(cur);//双端队列入队cur=cur.next;}cur=head;//指针又回到头节点for(int i=0;!deque.isEmpty();i++,cur=cur.next,cur.next=null) {cur.next=i%2==0?deque.removeFirst():deque.removeLast();}
}
}

Deque的用法：
1.Deque的介绍

public interface Deque<E> extends Queue<E>

Deque是一个双端队列接口，继承来自Queue接口
Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque，但是一般常用LinkedList实现接口。
（1）一般场景
LinkedList 大小可变的链表双端队列，允许元素为null
ArrayDeque 大小可变的数组双端队列，不允许null
（2）并发场景
LinkedBlockingDeque如果队列为空时，获取操作将会阻塞，知道有元素添加
定义的函数
Deque实现了双向队列，队列，和栈的功能
普通队列

Deque<E> deque=new LinkedList<>()

双端队列

Deque<E> deque=new LinkedList<>()

堆栈

Deque<E> deque=new LinkedList<>()