首页 > 代码库 > [leetcode]Partition List

[leetcode]Partition List

2024-07-13 02:27:19   223人阅读

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.

算法思路：

维护两个指针，一个指向带插入位置的前驱，一个顺序遍历list，遇到>=x的节点，next，遇到<x的就把它插入到上一个指针的后面。第一个节点<x时候，需要特殊处理

 1 public class Solution { 2     public ListNode partition(ListNode head, int x) { 3         if (head == null || head.next == null)    return head; 4         ListNode hhead = new ListNode(0); 5         hhead.next = head; 6         ListNode pre = hhead; 7         ListNode tail = hhead; 8         while (tail.next != null) { 9             if (tail.next.val < x) {//第一个节点特殊处理10                 if(tail == hhead){11                     pre = pre.next;12                     tail = tail.next;13                     continue;14                 }15                 ListNode tem = tail.next;16                 tail.next = tem.next;17                 tem.next = pre.next;18                 pre.next = tem;19                 pre = pre.next;20                 if(tail.val < x){21                     tail = tail.next;22                 }23             } else24                 tail = tail.next;25         }26         return hhead.next;27     }28 }

感觉这道题做的很垃圾。。。。


联系
我们