Daily Archives: March 7, 2013

Leetcode: Implement strStr()

Posted on by
Reply

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

public String strStr(String haystack, String needle) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(needle==null){
            return haystack;
        }

        int start = 0;
        int index1 = 0;
        int index2 = 0; 
        while(index1<haystack.length() && index2<needle.length()){
            if(haystack.charAt(index1)==needle.charAt(index2)){
                index1++;
                index2++;                
            }else{
                start++;
                index1=start;
                index2=0;

            }
        }
        if(index2==needle.length() && index1-start==needle.length()){
            return haystack.substring(start);
        }else{
            return null;
        }
    }
FacebookTwitterGoogle+Share

Leetcode: Merge Two Sorted Lists

Posted on by
Reply

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Start typing your Java solution below
        // DO NOT write main() function
        //a fake head
        //we should return head.next at the end
        ListNode head = new ListNode(0);
        ListNode newRunner = head;
        ListNode runner1 = l1;
        ListNode runner2 = l2;

        while(runner1!=null && runner2!=null){
            if(runner1.val<=runner2.val){
                newRunner.next = runner1;
                runner1 = runner1.next;
            }else{
                newRunner.next = runner2;
                runner2 = runner2.next;
            }
            newRunner = newRunner.next;
        }

        newRunner.next = runner1==null?runner2:runner1;
        return head.next;

    }