头条面试--单链表操作
题目
有一个链表，奇数位是升序，偶数位是降序，现在需要对其进行全部为升序，要求时间复杂度O(n)
注
这里只是为了演示，所以只是列举了几个，真是案例中肯定不是几个数据几点的链表，
思路
- 把链表按照奇数位和偶数位进行拆分，拆分成两个链表，
- 然后对偶数位的链表进行反转
- 然后合并两个列表
java代码实现
/** * @auther: lawt * @date: 2018/11/4 08 * @Description: 结点信息 */ public class Node { /** * 为了方便，这两个变量都使用public，而不用private就不需要编写get、set方法了。 * 存放数据的变量，简单点，直接为int型 */ public int data; /** * 存放结点的变量,默认为null */ public Node next; /** * 构造方法，在构造时就能够给data赋值 */ public Node(int data) { this.data = data; } } /** * @auther: lawt * @date: 2018/11/6 10 * @Description: 链表的奇数位升序，偶数位降序，对链表进行排序 * 1 7 2 6 3 5 4 * 时间复杂度是O(n) * 分成三步 * 1：按照奇数位和偶数位进行拆分成两个链表 * 2：对偶数位链表进行反转 * 3：合并两个链表 */ public class Interview1 { /** * 按照奇数位和偶数位进行拆分成两个链表 */ 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) { //奇数位 if (cur1 == null) { cur1 = head; head1 = cur1; } else { cur1.next = head; cur1 = cur1.next; } } else { //偶数位 if (cur2 == null) { cur2 = head; head2 = cur2; } else { cur2.next = head; cur2 = cur2.next; } } head = head.next; count++; } cur1.next = null; cur2.next = null; return new Node[]{head1, head2}; } /** * 对链表进行反转 */ public static Node reversal(Node head) { if (head == null || head.next == null) { return head; } Node prev = null; Node current = head; while (current != null) { Node next = current.next; current.next = prev; prev = current; current = next; } return prev; } /** * 合并两个有序链表 */ public static Node mergeTwoList(Node head1, Node head2) { //递归结束条件 if (head1 == null && head2 == null) { return null; } if (head1 == null) { return head2; } if (head2 == null) { return head1; } //合并后的链表 Node head = null; if (head1.data > head2.data) { //把head较小的结点给头结点 head = head2; //继续递归head2 head.next = mergeTwoList(head1, head2.next); } else { head = head1; head.next = mergeTwoList(head1.next, head2); } return head; } public static void main(String[] args) { Node head = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); Node node5 = new Node(5); Node node6 = new Node(6); Node node7 = new Node(7); head.next = node7; node7.next = node2; node2.next = node6; node6.next = node3; node3.next = node5; node5.next=node4; Node[] nodes = getList(head); Node node = reversal(nodes[1]); Node m = mergeTwoList(nodes[0], node); while (m != null) { System.out.print(m.data + " "); m = m.next; } } }
运行结果
