Partition List（将单链表进行分区）】

【LeetCode-面试算法经典-Java实现】【086-Partition List（将单链表进行分区）】

分类：LeetCode

【086-Partition List（将单链表进行分区）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题

　　Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. 　　You should preserve the original relative order of the nodes in each of the two partitions. 　　For example, 　　Given 1->4->3->2->5->2 and x = 3, 　　return 1->2->2->4->3->5.

题目大意

　　给定一个单链表和一个值x，将链表分成小于等于x的部分和大于x的部分。同时保持链表原来的相对顺序。

解题思路

　　创建两个链表a，b，将原来链表中的每个结点，小于等于x的结点放在a链表的末尾，，如果是大于就放在b的末尾，最后将b的头结点接到a末尾。

代码实现

结点类

public class ListNode {int val;ListNode next;ListNode(int x) { val = x; }}

算法实现类

public class Solution {public ListNode partition(ListNode head, int x) {ListNode le = new ListNode(0); // 小于x的链表ListNode ge = new ListNode(0); // 大于等于x的链表ListNode t1 = le;ListNode t2 = ge;ListNode p = head;while (p != null) {if (p.val < x) {t1.next = p;t1 = p;} else {t2.next = p;t2 = p;}p = p.next;}t2.next = null;// 说明小于的链表上有数据if (t1 != le) {t1.next = ge.next;head = le.next;} else {head = ge.next;}return head;}}评测结果

　　点击图片，鼠标不释放，拖动一段位置，释放后在新的窗口中查看完整图片。

特别说明欢迎转载，转载请注明出处【】

上一篇【LeetCode-面试算法经典-Java实现】【083-Remove Duplicates from Sorted List（排序的单链表中删除重复的结点）】下一篇【LeetCode-面试算法经典-Java实现】【088-Merge Sorted Array（合并排序数组）】

顶1踩0

世俗的纷扰，生活的琐碎使人精疲力尽，

相关文章：

你感兴趣的文章：

标签云：