題目描述：一個鏈表，特點是奇數位升序偶數位降序，使得鏈表變成升序的。

• 分析
• 代碼
• • 節點類:
  • main方法:
  • 初始化方法：
  • 按照奇偶位拆分成兩個鏈表:
  • 反轉鏈表:
  • 合并兩個有序鏈表(非遞歸)：
  • 合并兩個有序鏈表(遞歸)：

分析

這道題可以分成三步：
首先根據奇數位和偶數位拆分成兩個鏈表。
然后對偶數鏈表進行反轉。
最后將兩個有序鏈表進行合并（合并兩種實現方式一種是遞歸另外一種是非遞歸）。

代碼

節點類:

class Node {int value;Node next;Node(int x) {value = x;next = null;} }

main方法:

public static void main(String[] args) {Node head = init();Node[] lists = getLists(head);Node head1 = lists[0];Node head2 = lists[1];head2 = reverseList(head2);// head = CombineList(head1, head2);head = mergeTwoLists(head1, head2);while(head != null) {System.out.println(head.value);head = head.next;} }

初始化方法：

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[] getLists(Node head) {Node head1 = null;Node head2 = null;Node cur1 = null;Node cur2 = null;int count = 1;while(head != null) {if(count%2 == 1) {if(head1 == null) {cur1 = head;head1 = cur1;} else {cur1.next = head;cur1 = cur1.next;}} else {if(head2 == null) {cur2 = head;head2 = cur2;} else {cur2.next = head;cur2 = cur2.next;}}count++;head = head.next;}cur1.next = null;cur2.next = null;Node[] list = new Node[]{head1,head2};return list; }

反轉鏈表:

public static Node reverseList(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 CombineList(Node head1, Node head2) {if(head1 == null || head2 == null) {return head1 != null ? head1 : head2;} Node head = head1.value < head2.value ? head1 : head2;Node cur1 = head == head1 ? head1 : head2;Node cur2 = head == head1 ? head2 : head1;Node pre = null;Node next = null;while(cur1 != null && cur2 != null) {if(cur1.value < cur2.value) {pre = cur1;cur1 = cur1.next;} else {next = cur2.next;pre.next = cur2;cur2.next = cur1;pre = cur2;cur2 = next;}}pre.next = cur1 == null ? cur2 : cur1;return head; }

合并兩個有序鏈表(遞歸)：

public static Node mergeTwoLists(Node l1, Node l2) {if(l1 == null || l2 == null){return l1 != null ? l1 : l2;}Node head = null;if(l1.value > l2.value){head = l2;head.next = mergeTwoLists(l1,l2.next);} else {head = l1;head.next = mergeTwoLists(l1.next,l2);}return head; }

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。