Is there a technique to write elegant code for this kind of problems?


  • 0

    This problem isn't tagged hard for nothing. It doesn't require any fancy algorithms. It doesn't require any fancy data structures (in fact, you're explicitly forbidden to use those). It only requires basic understanding of one of the simplest data structures. It is very easy to implement. But it is very tricky to implement it right, and even more trickier to implement it in elegant way. After a few minutes of coding you end up with lots of loops and checks and whatnot. So I was wondering whether there are some techniques that can make such problems easier to write correctly and in elegantly. Some I can think of right away:

    • use sentinels to avoid plaguing null checks;
    • use loop invariant to make sure your algorithm is correct;
    • split your algorithm into smaller functions if it gets complicated—you can always merge them back if you really want to, once you've finished debugging all the pieces;
    • the last, but not the least: forget about premature optimization, make it right first.

    But it still feels lacking somehow. The best code I ended up with is below and even there I use this ugly helper class which probably shouldn't be needed at all, and if I try to merge everything into a single function, I'll end up with lots of variables, many of which are probably redundant. Take this prev field of the helper class. The only reason I need it is because I can't do reverse(group.head, k, prev.tail) in the last moment fixup (the if (group.size < k) part) because at that moment prev will be equal to group, as the loop isn't executed after the last prev = group assignment. Or I can use if (group.size == k) { prev = group; } in the loop, but that's ugly too (and one more branch).

    Is there a book or something on writing elegant code? Sometimes it feels outright impossible (imagine an elegant red-black tree implementation!), but sometimes you see people writing complicated DP loops in four lines or so. Of course it's something you learn with experience, but maybe there's more to it?

    public ListNode reverseKGroup(ListNode head, int k) {
        if (k <= 1 || head == null) {
            return head;
        }
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        Group group = null, prev = new Group(null, sentinel, sentinel, 1);
        for (ListNode node = head; node != null; node = group.tail.next, prev = group) {
            group = reverse(node, k, prev.tail);
        }
        if (group.size < k) {
            reverse(group.head, k, group.prev);
        }
        return sentinel.next;
    }
    
    private static Group reverse(ListNode head, int k, ListNode previous) {
        ListNode tail = head, node = head, prev = null;
        int len;
        for (len = k; len > 0 && node != null; --len) {
            ListNode next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        tail.next = node;
        previous.next = prev; // prev is now the new head
        return new Group(previous, prev, tail, k - len);
    }
    
    private static class Group {
        final ListNode prev, head, tail;
        final int size;
        
        Group(ListNode prev, ListNode head, ListNode tail, int size) {
            this.prev = prev;
            this.head = head;
            this.tail = tail;
            this.size = size;
        }
    }
    

Log in to reply
 

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