给定一个单链表 L 的头节点 head ,单链表 L 表示为:
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
思路: 这题一开始我就想着我只想着对链表进行操作,建立两个子链表,一个奇数个节点顺序插入,一个偶数个节点头插逆序,中间节点保存为尾节点进行拼接,这样做真的很麻烦,弄了很久还是没有写出来,看了官方的题解,恍然大悟。因为链表不能随机访问,对这种奇数偶数中间节点的处理实在是不方便,于是我们将链表每一个节点遍历然后放入ArrayList顺序表中,之后再按照数组的下标来进行处理。
代码:
class Solution {
public void reorderList(ListNode head) {
ArrayList<ListNode> list=new ArrayList();
if(head==null) {
return ;
}
ListNode cur=head;
while(cur!=null) {
list.add(cur);
cur=cur.next;
}
int right=list.size()-1;
int left=0;
ListNode l=new ListNode();
cur=l;
while(right>left) {
ListNode leftNode=list.get(left);
ListNode rightNode=list.get(right);
cur.next=leftNode;
cur=leftNode;
leftNode.next=null;
cur.next=rightNode;
cur=rightNode;
rightNode.next=null;
right--;
left++;
}
if(list.size()%2!=0) {
ListNode tailNode=list.get(list.size()/2);
cur.next=tailNode;
tailNode.next=null;
}
head=l.next;
}
}
官方题解比我的代码精简很多。
官方题解:
class Solution {
public void reorderList(ListNode head) {
if (head == null) {
return;
}
List<ListNode> list = new ArrayList<ListNode>();
ListNode node = head;
while (node != null) {
list.add(node);
node = node.next;
}
int i = 0, j = list.size() - 1;
while (i < j) {
list.get(i).next = list.get(j);
i++;
if (i == j) {
break;
}
list.get(j).next = list.get(i);
j--;
}
list.get(i).next = null;
}
}
给你链表的头结点 head,请将其按升序排列并返回排序后的链表 。
思路: 因为有了上一题的启发,这一题我就还是想用ArrayList来解决问题,遍历链表使用ArrayList来保存每个节点,之后使用冒泡排序根据节点值来进行排序。排序完成后按顺序链接每一个节点。但是很遗憾,虽然链表长度有限时测试用例能够通过,但是当链表长度过长时就会超时,呜呜。看了官方题解要用递归求解,我对递归的掌握还不够,决定过几天再刷此题。下面贴出我的超时的笨方法。
代码:
class Solution {
public ListNode sortList(ListNode head) {
if(head==null) {
return null;
}
ArrayList<ListNode> list =new ArrayList();
ListNode cur=head;
while(cur!=null) {
list.add(cur);
cur=cur.next;
}
for(int i=0;i<list.size()-1;i++) {
for(int j=0;j<list.size()-i-1;j++) {
if(list.get(j).val>=list.get(j+1).val) {
ListNode temp=list.get(j);
list.set(j,list.get(j+1));
list.set(j+1,temp);
}
}
}
ListNode temp =new ListNode();
cur=temp;
for(int i=0;i<list.size();i++) {
cur.next=list.get(i);
cur=cur.next;
}
cur.next=null;
return temp.next;
}
}