題目描述：一個鏈表，奇數(shù)位升序偶數(shù)位降序，讓鏈表變成升序的。

比如：1 8 3 6 5 4 7 2 9，最后輸出1 2 3 4 5 6 7 8 9。

分析：

這道題可以分成三步：

首先根據(jù)奇數(shù)位和偶數(shù)位拆分成兩個鏈表。

然后對偶數(shù)鏈表進(jìn)行反轉(zhuǎn)。

最后將兩個有序鏈表進(jìn)行合并。

?

package com.xxx;/*/ 一個鏈表，奇數(shù)位升序偶數(shù)位降序，讓鏈表變成升序的。比如：1 8 3 6 5 4 7 2 9，最后輸出1 2 3 4 5 6 7 8 9*/ /*** create by ziqiiii*/ public class Test {public static class Node {int val;Node next;Node(int x) { val = x; }}public static void main(String[] args){Node head = init();System.out.println("original:");printNode(head);Node[] nodes = getList(head);Node node1 = nodes[0];Node node2 = nodes[1];System.out.println("node1:");printNode(node1);System.out.println("node2:");printNode(node2);node2 = reverse(node2);System.out.println("reverse node2:");printNode(node2);Node result = mergeNode(node1,node2);System.out.println("result:");printNode(result);}public static void printNode(Node head){System.out.print(head.val);head=head.next;while(head!=null){System.out.print("->"+head.val);head=head.next;}System.out.println();}public static Node init(){Node node1 = new Node(1);Node node2 = new Node(8);Node node3 = new Node(3);Node node4 = new Node(6);Node node5 = new Node(5);Node node6 = new Node(4);Node node7 = new Node(7);Node node8 = new Node(2);Node node9 = new Node(9);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;node5.next = node6;node6.next = node7;node7.next = node8;node8.next = node9;return node1;}public static Node[] getList(Node head){Node head1=null;Node head2=null;Node cur1 = null;Node cur2 = null;int count=1;while(head != null){if(count % 2 ==1){ //奇數(shù)位, 升序if(cur1==null){head1=head;cur1=head1;}else{cur1.next=head;cur1=head;}}else{ //偶數(shù)位, 降序if(cur2==null){head2=head;cur2=head2;}else{cur2.next=head;cur2=head;}}head=head.next;count++;}cur1.next=null;//一定要給兩個新的鏈表結(jié)尾nullcur2.next=null;Node[] nodes = new Node[]{head1,head2};return nodes;}public static Node reverse(Node head){Node pre = null;Node next = null;while(head != null){next = head.next;head.next=pre;pre=head;head=next;}return pre;}public static Node mergeNode(Node node1,Node node2){if(node1==null){return node2;}if(node2==null){return node1;}Node head = null;Node cur = null;if(node1.val<=node2.val){head=node1;node1=node1.next;head.next=null;cur = head;}else{head=node2;node2=node2.next;head.next=null;cur = head;}while(node1!=null && node2!=null){if(node1.val<=node2.val){cur.next=node1;node1=node1.next;cur=cur.next;cur.next=null;}else{cur.next=node2;node2=node2.next;cur=cur.next;cur.next=null;}}if(node1 !=null){cur.next=node1;}if(node2 !=null){cur.next=node2;}return head;} }

?

?

?

?

參考自：[算法]頭條面試—奇數(shù)位升序偶數(shù)位降序鏈表排序

總結(jié)

以上是生活随笔為你收集整理的奇数位升序偶数位降序链表排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。