Write a C function that reverses a single-linked list

Question

yogev · Accepted Answer

JAVA:

	public static Node reverse(Node node){
		// if the list is a single node -> nothing to reverse
		if(node.next == null)
			return node;
		// else there are 2 or more nodes 
		Node newHead = node.next;
		// mark the end of the list
		node.next = null;
		Node newHeadNext;
		while(true){
			// if there is continuity after newHead
			if(newHead.next != null){
				newHeadNext = newHead.next;
				// the reverse move
				newHead.next = node;
				// move the nodes to their new place
				node = newHead;
				newHead = newHeadNext;
			}
			else{
				// the reverse move
				newHead.next = node;
				return newHead;
			}
			
		}
	}

Utilisateur anonyme · Answer

Node*
Reverse(Node *head)
{
  Node *prev = NULL, *next = NULL;

  while (NULL != head) {
    next = head->next;
    head->next = prev;
    prev = head;
    head = next;
    if (NULL != next) {
       next = next->next;
    }
  }

  return prev;
}

Utilisateur anonyme · Answer

You can use 2 queues to simulate a stack, push all elements into stack and pop (LIFO) into the second queue. (I don't think is really efficient, but a different way).

Another solution is a recursive function:
Node * reverse( Node * ptr , Node * previous)
{
    Node * temp;
    if(ptr->next == NULL) {
        ptr->next = previous;
        return ptr;
    } else {
        temp = reverse(ptr->next, ptr);
        ptr->next = previous;
        return temp;
    }
}
reversedHead = reverse(head, NULL);

IBM

Question d’entretien chez IBM

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois