Java Simple Modularised code for re-use in other problems


  • 1
    S

    My solution for Palindrome Linked List.
    As other's have suggested, I too have broken the list into two then reversed the second partition and compared it with the first partition to see if it is a palindrome. However I have modularized the code by breaking these steps into a separate function, so that they can be re-used in other problems, as we already have reverse a list, and compare two lists.

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public static boolean isPalindrome(ListNode head) {
    		if(head == null || head.next == null) {
    			return true;
    		}
    
    		ListNode dummy = new ListNode(0);
    		dummy.next = head;
    
    		ListNode newHead = partitionList(dummy, null);
    
    		ListNode reverseNewHead = reverseList(newHead);
    
    		return areListsEqual(dummy.next, reverseNewHead);
    	}
    
    	public static boolean areListsEqual(ListNode head1, ListNode head2) {
    		while(head1 != null && head2 != null) {
    			if(head1.val == head2.val) {
    				head1 = head1.next;
    				head2 = head2.next;
    			}
    			else {
    				return false;
    			}
    		}
    		return true;
    	}
    
    	public static ListNode partitionList(ListNode head, ListNode newHead) {
    
    		ListNode slow = head;
    		ListNode fast = head;
    
    		while(fast.next != null && fast.next.next != null) {
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    
    		newHead = slow.next;
    		slow.next = null;
    
    		return newHead;
    	}
    
    	public static ListNode reverseList(ListNode head) {
    		ListNode reverse = null;
    		while(head != null) {
    			ListNode next = head.next;
    			head.next = reverse;
    			reverse = head;
    			head = next;
    		}
    
    		return reverse;
    	}
    }
    

    If we use a recursion based approach for reversing the list, the time complexity will increase.
    ListNode reverse = null; before passing it to the function.

    public static ListNode reverseList(ListNode head, ListNode reverse) {
    		if(head == null) {
    			return reverse;
    		}
    
    		ListNode next = head.next;
    		head.next = reverse;
    		return reverseList(next, head);
    	}
    

    Thank you.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.