changeset 140:76602668b9f5

Reverse linked list in-place.
author Oleksandr Gavenko <gavenkoa@gmail.com>
date Sat, 17 Mar 2018 12:34:42 +0200
parents 9dfc87dc789c
children 5e8a2271c86d
files ed00c7c3-a71e-4ed2-bfbb-ff2ac918960e/index.rst
diffstat 1 files changed, 99 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ed00c7c3-a71e-4ed2-bfbb-ff2ac918960e/index.rst	Sat Mar 17 12:34:42 2018 +0200
@@ -0,0 +1,99 @@
+
+==============================
+ Reverse linked list in-place
+==============================
+:created: 2018-03-17 12:22
+:updated: 2018-03-17
+:tags: c, interview
+
+It is common interview programming task to reverse singly linked list in-place.
+
+For example it mentioned here:
+
+https://www.joelonsoftware.com/2006/10/25/the-guerrilla-guide-to-interviewing-version-30/
+  The Guerrilla Guide to Interviewing (version 3.0).
+
+At interview with online editor I spent 40 min to complete task with many time spent debugging::
+
+  reverse(list);
+  print(list);
+
+where I should write::
+
+  list = reverse(list);
+  print(list);
+
+Today I implemented it in 15 min::
+
+  #include <stdio.h>
+  #include <stdlib.h>
+  #include <assert.h>
+
+  typedef struct list_t {
+      int val;
+      struct list_t *next;
+  } list_t;
+
+  list_t * list_make(int size) {
+      assert(size > 0);
+      list_t *head = NULL;
+      for (int i = 0; i < size; i++) {
+          list_t *tail = head;
+          head = malloc(sizeof(list_t));
+          head->next = tail;
+      }
+      return head;
+  }
+
+  void list_incr_fill(list_t *head) {
+      for (int i = 1; head != NULL; i++, head = head->next) {
+          head->val = i;
+      }
+  }
+
+  void list_print(list_t *head) {
+      while (head != NULL) {
+          printf("%d ", head->val);
+          head = head->next;
+      }
+      puts("");
+  }
+
+  list_t* list_reverse(list_t *head) {
+      list_t *tail = head;
+      head = NULL;
+      while (tail != NULL) {
+          list_t *old_head = head;
+          head = tail;
+          tail = tail->next;
+          head->next = old_head;
+      }
+      return head;
+  }
+
+  int main() {
+      list_t *my = list_make(5);
+      list_incr_fill(my);
+      list_print(my);
+      my = list_reverse(my);
+      list_print(my);
+      return 0;
+  }
+
+To run I use::
+
+  gcc -o rev.exe rev.c && ./rev.exe
+
+The problem was that I forgot syntax how to declare self reference in structure declaration, below
+is wrong syntax::
+
+  typedef struct {
+      int val;
+      list_t *next;
+  } list_t;
+
+and forgot header name for ``assert()``.
+
+https://en.wikibooks.org/wiki/Data_Structures/Singly_Linked_Lists
+  Singly Linked Lists.
+