DEV Community

Tanuja V
Tanuja V

Posted on • Edited on

6 1 2 1

Partition List | LeetCode | Java

Algorithm

  1. Initialize two dummy nodes: lessHead and highHead to serve as heads for two separate lists, one for nodes with values less than x and one for nodes with values greater than or equal to x.
  2. Initialize pointers less and high to keep track of the tail of the two lists respectively.
  3. Iterate through the original linked list (head) using a temporary pointer temp.
  4. For each node in the original list:
    • If the value of the current node (temp.val) is less than x, append it to the less list.
    • If the value of the current node is greater than or equal to x, append it to the high list.
  5. Connect the tail of the less list to the head of the high list.
  6. Return the head of the less list, which now contains the partitioned linked list.

Code

class Solution {
    public ListNode partition(ListNode head, int x) {

        ListNode lessHead = new ListNode(0);
        ListNode highHead = new ListNode(0);

        ListNode less = lessHead, high = highHead;

        ListNode temp = head;

        while(temp!=null){
            if(temp.val<x){
                less.next = new ListNode(temp.val);
                less = less.next;
            }
            else{
                high.next = new ListNode(temp.val);
                high = high.next;
            }
            temp = temp.next;
        }

        less.next = highHead.next;

        return lessHead.next;
    }
}
Enter fullscreen mode Exit fullscreen mode

Thanks for reading :)
Feel free to comment and like the post if you found it helpful
Follow for more 🤝 && Happy Coding 🚀

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay