LeetCodeのLinkedList解いてみた

解いたコード

• @koheiarai94さんが挙げていた問題の中でLinkedListカテゴリの問題を解いてみた
  • コーディング面接対策のために解きたいLeetCode 60問 | 新井康平
• C#で書いてます

Problem1

leetcode.com

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public bool HasCycle(ListNode head) {
        ListNode current = head;
        HashSet<ListNode> hashSet = new HashSet<ListNode>();
        while (current != null) {
            if (hashSet.Add(current) == false) {
                return true;
            }
            current = current.next;                
        }
        return false;
    }
}

補足

• 公式の解答をみると別解があるらしい
• 私の解だとHashSetに要素の長さ分(Space complexity)格納することになるが(つまりO(n))、これをO(1)にできるらしい
• 一応そのコードを書いておく

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public bool HasCycle(ListNode head) {
        if (head == null) {
            return false;            
        }

        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            if (slow == fast) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }
}

• なるほどなーこれは思いつかん

Problem2

leetcode.com

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode DetectCycle(ListNode head) {
       ListNode current = head;
        HashSet<ListNode> hashSet = new HashSet<ListNode>();
        while (current != null) {
            if (hashSet.Add(current) == false) {
                return current;
            }
            current = current.next;                
        }
        return null; 
    }
}

Problem3

leetcode.com

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        ListNode currentListNode = head;
        while(currentListNode != null && currentListNode.next != null) {
            if (currentListNode.val == currentListNode.next.val) {
                currentListNode.next = currentListNode.next.next;                
            } else {
                currentListNode = currentListNode.next;
            }
        }
        return head;
    }
}

Problem4

leetcode.com

Solution

• prev使うところまでは思いついたんだが正解には至らなかった・・
• ということで下記のpythonコードを参考にc#にしました
  • https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/discuss/509070/python-solution
• 連続している数値はすっ飛ばすところがミソですな

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        ListNode current = head;
        ListNode prev = new ListNode(0);
        ListNode ret = prev;
        ret.next = prev.next = current;
        while (current != null && current.next != null) {
            ListNode next = current.next;
            if (current.val == next.val) {
                while (next.next != null && next.val == next.next.val) {
                    next = next.next;                    
                }
                prev.next = current = next.next;
                if (current == null) {
                    return ret.next;
                }
            } else {
                prev = current;
                current = next;
            }
        }
        return ret.next;
    }
}