{"id":352,"date":"2013-03-22T17:06:56","date_gmt":"2013-03-23T00:06:56","guid":{"rendered":"http:\/\/192.168.1.2\/wordpress\/?p=352"},"modified":"2013-03-24T04:17:00","modified_gmt":"2013-03-24T11:17:00","slug":"chapter-2-linked-lists","status":"publish","type":"post","link":"http:\/\/cywang.no-ip.org\/wordpress\/?p=352","title":{"rendered":"Chapter 2. Linked Lists"},"content":{"rendered":"
    \n
  1. \n\t\tWrite code to remove duplicates from an unsorted linked list.
    \n\t\tFOLLOW UP
    \n\t\tHow would you solve this problem if a temporary buffer is not allowed?\n\t<\/li>\n
  2. \n\t\tImplement an algorithm to find the nth to last element of a singly linked list.\n\t<\/li>\n
  3. \n\t\tImplement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
    \n\t\tEXAMPLE
    \n\t\tInput: the node c from the linked list a->b->c->d->e
    \n\t\tResult: nothing is returned, but the new linked list looks like a->b->d->e<\/p>\n

    \n\t\n<\/p>\n<\/li>\n

  4. \n\t\tWrite code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.\n\t<\/li>\n
  5. \n\t\tYou have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
    \n\t\tEXAMPLE
    \n\t\tInput: (7->1->6) + (5->9->2). That is, 617 + 295.
    \n\t\tOutput: 2->1->9. That is, 912.
    \n\t\tFOLLOW UP
    \n\t\tSuppose the digits are stored in forward order. Repeat the above problem.
    \n\t\tEXAMPLE
    \n\t\tInput: (6->1->7) + (2->9->5). That is, 617 + 295.
    \n\t\tOutput: 9->1->2. That is, 912.\n\t<\/li>\n
  6. \n\t\tGive a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
    \n\t\tDEFINITION
    \n\t\tCircular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
    \n\t\tEXAMPLE
    \n\t\tInput: A->B->C->D->E->C [the same C as earlier]
    \n\t\tOutput: C\n\t<\/li>\n
  7. \n\t\tImplement a function to check if a linked list is a palindrome.\n\t<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

    Write code to remove duplicates from an unsorted linked list. FOLLOW UP How would you solve this problem if a temporary buffer is not allowed? Implement an algorithm to find the nth to last element of a singly linked list. … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[6],"tags":[],"class_list":["post-352","post","type-post","status-publish","format-standard","hentry","category-cracking-the-coding-interview"],"_links":{"self":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/352","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=352"}],"version-history":[{"count":4,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/352\/revisions"}],"predecessor-version":[{"id":367,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/352\/revisions\/367"}],"wp:attachment":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=352"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=352"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=352"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}