首页 > 代码库 > 【原创】leetCodeOj ---Partition List 解题报告

【原创】leetCodeOj ---Partition List 解题报告

原题地址:

https://oj.leetcode.com/problems/partition-list/

 

题目内容:

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.

 

方法:

链表的基本功。

维护两个带头结点的链表,一个存 < ,一个存 >=,然后一个连接就可以了。

 

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    public ListNode partition(ListNode head, int x) {        if (head == null)            return null;        ListNode lessHead = new ListNode(0);        ListNode moreHead = new ListNode(0);        ListNode lessTail = lessHead;        ListNode moreTail = moreHead;        ListNode tmp = null;        while (head != null)        {            tmp = head;            head = head.next;            tmp.next = null;                        if (tmp.val < x)            {                lessTail.next = tmp;                lessTail = lessTail.next;            }            else            {                moreTail.next = tmp;                moreTail = moreTail.next;            }        }        if (lessHead.next != null)            lessTail.next = moreHead.next;        else            lessHead.next = moreHead.next;        return lessHead.next;    }}

 

【原创】leetCodeOj ---Partition List 解题报告