2021-07-09 链表中 非常考验基本功的一道题目

2021-07-09 链表中 非常考验基本功的一道题目

基本功

​​单链表奇数递增偶数递减，重排后使之升序​​​​链表分隔​​

单链表奇数递增偶数递减，重排后使之升序

题目：单链表奇数递增偶数递减，重排后使之升序，举例：1->8->3->6->5->4->7->2->9 变成 1->2->3->4->5->6->7->8->9

这道题很考验基本功，写个几遍，基本上其他链表题的细节问题都能cover。做这个题的快慢，决定刷题的熟练度。

思路：链表的分离：将单链表的奇数节点变成一个链表(1->3->5->7->9)，偶数节点变成一个链表(8->6->4->2)链表的逆转：逆转偶数链表(2->4->6->8)链表的归并：将奇数链表(1->3->5->7->9)和偶数链表(2->4->6->8)，归并排序

按照上面的思路去写，其中第一步可以有多种方法，第二步、第三步比较固定。第一步可以

代码：

public class Six { //写一个链表，奇数是增，偶数是递减。例如（1,8,3,6,5,4,7,2,9）变成 1-2-3-4-5-6-7-8-9 static class Node{ int val; Node next; public Node(int val) { this.val = val; this.next=null; } } public static Node Sort(Node root){ //将此链表拆分成2个，奇数组成一个，偶数组成一个 Node descNode=root.next; Node desc=descNode; Node inscNode =root; Node insc =inscNode; while (desc!=null&&desc.next!=null){ insc.next=insc.next.next;//需要注意，这行和下一行不能反 desc.next=desc.next.next; desc=desc.next; insc=insc.next; } if (desc!=null){ insc.next=null; } //desc 链表翻转 descNode =reverse(descNode); //归并排序 return merge(descNode,inscNode); } private static Node reverse(Node descNode) { Node head = new Node(-1); while (descNode!=null){ Node temp =descNode; descNode=descNode.next; temp.next=head.next; head.next=temp; } return head.next; } private static Node merge(Node descNode, Node inscNode) { Node head = new Node(-1); Node p =head; while (descNode!=null&&inscNode!=null){ if (descNode.val>inscNode.val){ p.next=inscNode; inscNode=inscNode.next; }else { p.next=descNode; descNode=descNode.next; } p=p.next; } while (descNode!=null){ p.next=descNode; descNode=descNode.next; p=p.next; } while (inscNode!=null){ p.next=inscNode; inscNode=inscNode.next; p=p.next; } return head.next; } public static void main(String[] args) { Node head =new Node(1); Node head1 =new Node(8); Node head2 = new Node(3); Node head3 =new Node(6); Node head4 =new Node(5); Node head5 =new Node(4); Node head6 =new Node(7); Node head7 =new Node(2); Node head8 =new Node(9); head.next=head1; head1.next=head2; head2.next=head3; head3.next=head4; head4.next=head5; head5.next=head6; head6.next=head7; head7.next=head8; Node node =Sort(head); while (node!=null){ System.out.print(node.val+"--"); node=node.next; } }}

链表分隔

题目： 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前 ，你应当 保留 两个分区中每个节点的初始相对位置。 输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]

上面的描述我也看不懂。用上面例子表述，输入head = [1,4,3,2,5,2], x = 3，将这个链表拆成A B两个链表，A链表：[1,2,2]。 B链表：[4 ,3 ,5]。最后合并 ，输出结果为[1,2,2,4,3,5]

**思路：**类比上面那道题的链表分离，这个题也就很快有了答案，也是使用双指针的方式作答。

代码：

public ListNode partition(ListNode head, int x) { ListNode increase = new ListNode(-1); ListNode pIncrease=increase; ListNode descrease = new ListNode(-1); ListNode pDescrease=descrease; while (head!=null){ if (head.val>=x){ pIncrease.next=head; pIncrease=pIncrease.next; }else { pDescrease.next=head; pDescrease=pDescrease.next; } head=head.next; } pDescrease.next=increase.next; pIncrease.next=null; return descrease.next; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。