LeetCode-热题100-笔记-day21

24. 两两交换链表中的节点https://leetcode.cn/problems/swap-nodes-in-pairs/

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

代码思路

将奇数位置的节点和偶数位置的分开存放到队列中，然后分别出队列，奇数偶数各出一个直到出完为止； 

class Solution {public ListNode swapPairs(ListNode head) {//奇数节点队列Queue<ListNode> odd = new LinkedList<>();//偶数节点队列Queue<ListNode> even = new LinkedList<>();if(head==null||head.next==null){return head;}// 将奇数和偶数节点分开入队while(true){if(head!=null){odd.add(head);head=head.next;}if(head!=null){even.add(head);head=head.next;}else{//当head.next==null时结束whilebreak;}}// 头节点ListNode ans=new ListNode(-1);// 辅助节点ListNode cur=ans;// 出队while(!odd.isEmpty()||!even.isEmpty()){// 偶数位置先出if(!even.isEmpty()){cur.next=even.poll();cur=cur.next;}// 奇数位置出队if(!odd.isEmpty()){cur.next=odd.poll();cur=cur.next;}}cur.next=null;return ans.next;}
}

148. 排序链表https://leetcode.cn/problems/sort-list/

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

class Solution {public ListNode sortList(ListNode head) {ArrayList<Integer> list=new ArrayList<>();while(head!=null){list.add(head.val);head=head.next;}Integer[] nums=list.toArray(new Integer[0]);Arrays.sort(nums);ListNode ans=new ListNode(-1);ListNode cur=ans;for(int i=0;i<nums.length;i++){cur.next=new ListNode(nums[i]);cur=cur.next;}cur.next=null;return ans.next;}
}