题目描述

给定一个链表，和一个数值x，请对链表进行分割，使小于x的值全部放在x的左边。

示例：

5—4---6—2---8，x=5

你可以分割成：2—4---5—6---8

2，4在5的左边。

你也可以分割成：2—6---4—5---8

2，4在5的左边，尽管6大于5，且在5的左边，但你不用考虑大于5的值所在的位置。

假设你分割成：2—5---4—6---8

这样是不行的，因为4在5的右边了。

本题的解法很多，通过此题，可以充分的练习到链表的一些基本操作

解法1：双链表

思路很简单，一个链表专门记录小于x的值，一个链表专门记录大于x的值，然后用记录小值的链表连上记录大值的链表即可。

class Solution {
       public ListNode partition(ListNode head, int x) {
           ListNode dummyS = new ListNode(0);        ListNode small = dummyS;        ListNode dummyL = new ListNode(0);        ListNode large = dummyL;        while (head != null) {
               if (head.val < x) {
                   small.next = head;                small = small.next;            } else {
                   large.next = head;                large = large.next;            }            head = head.next;        }        large.next = null;        small.next = dummyL.next;        return dummyS.next;    }}

解法2：排序

很明显，这题不管x给什么，只需要对链表进行一次排序，既能满足题目要求，之前的题目中有练习过插入排序、归并排序，随便哪一种都可以，当然归并的效率更高一点。

class Solution {
       public ListNode partition(ListNode head, int x) {
           return sortList(head, null);    }    private ListNode sortList(ListNode head, ListNode tail) {
           //无法继续拆分的情况        if (head == null) {
               return null;        }        //无法继续拆分的情况        if (head.next == tail) {
               head.next = null;            return head;        }        //快慢指针找到中间节点        ListNode slow = head, fast = head;        while (fast != tail && fast.next != tail) {
               slow = slow.next;            fast = fast.next.next;        }        ListNode mid = slow;        //左边继续拆分        ListNode left = sortList(head, mid);        //右边继续拆分        ListNode right = sortList(mid, tail);        //有序链表合并        return merge(left, right);    }    private ListNode merge(ListNode left, ListNode right) {
           ListNode mergeNode = new ListNode();        ListNode help = mergeNode;        //比较两个链表当前的值，值小的链表就把引用赋给mergeNode，并向后移动一位重新赋值给自己，同时help指向值小的那个节点        while (left != null && right != null) {
               if (left.val < right.val) {
                   help.next = left;                left = left.next;            } else {
                   help.next = right;                right = right.next;            }            help = help.next;        }        //最后如果有剩余的节点，就一次性链上去         help.next = left == null ? right : left;        return mergeNode.next;    }}

解法3：头插法

道理也很简单，挨个遍历，遇到小于x值的节点，就插到头部

PS：Java中HashMap，jdk1.8之前，扩容时链表采用的就是头插法（存在死循环的问题，1.8改了）。

class Solution {
       public ListNode partition(ListNode head, int x) {
           ListNode dummy = new ListNode();        dummy.next = head;        while (head != null && head.next != null) {
               int nextVal = head.next.val;            if (nextVal < x) {
                   ListNode next = head.next;                head.next = head.next.next;                next.next = dummy.next;                dummy.next = next;            } else {
                   head = head.next;            }        }        return dummy.next;    }}

解法4：原地删除

按照删除节点的方式，遇到小于x值的节点，就从原链表中删除，并添加到新的链表中，这样一次遍历结束后，只要把新的链表连上原链表即可。

class Solution {
       public ListNode partition(ListNode head, int x) {
           ListNode dummy = new ListNode();        dummy.next = head;        ListNode smallDummy = new ListNode();        ListNode small = smallDummy;        //和删除节点的套路一样，先处理头节点满足条件的情况        while (head != null) {
               if (head.val >= x) {
                   break;            }            small.next = new ListNode(head.val);            small = small.next;            head = head.next;        }        //删除        ListNode cur = head;        ListNode pre = null;        while (cur != null) {
               if (cur.val < x) {
                   pre.next = cur.next;                small.next = new ListNode(cur.val);                small = small.next;            } else {
                   pre = cur;            }            cur = cur.next;        }        small.next = head;        return smallDummy.next;    }}

除了排序，要根据排序方法本身的时间复杂度计算，其余的三种方式都是O(n)的时间复杂度。

转载地址：http://ahlrb.baihongyu.com/

你可能感兴趣的文章