Problem Set 1: Reverse a Linked List, Partition a Linked List

problemset1-reverse.java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 
 //build two linkedlists, the smallers, the biggers|equals, attach head to tail at the end;
public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode head1 = null;
        ListNode curr1 = null;
        ListNode head2 = null;
        ListNode curr2 = null;
        ListNode curr = head;
        while (curr != null){
            if (curr.val < x){
                ListNode add = new ListNode(curr.val);
                if (head1 == null){
                    head1 = add;
                } else {
                    curr1.next = add;
                }
                curr1 = add;
            } else {
                ListNode add = new ListNode(curr.val);
                if (head2 == null){
                    head2 = add;
                } else {
                    curr2.next = add;
                }
                curr2 = add;
            }
            curr = curr.next;
        }
        ListNode ans = head1;
        if(curr1!=null) {
            curr1.next = head2;
        }
        else if (head1 == null) {
            ans = head2;
        }
        return ans;
        
    }
}

reverseLL.java

Node Reverse(Node head) {
    Node prev = null;
    Node curr = head;
    while (curr != null){
        Node temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
    }
    return prev;

}