Thread: How to reverse a unidirectional linked list

  1. #1
    Registered User
    Join Date
    May 2013
    Posts
    228

    How to reverse a unidirectional linked list

    Hi.
    I was assigned to reverse a unidirectional linked list in C, where I'm not allowed to make a copy of the given linked list, or to change the actual data.
    The only thing I'm allowed to do is to manipulate the list's pointers.
    After doing some thinking and scribbling on a piece of paper, I came up with this:


    • Initialize three pointers: p1,p2,p3, for the first, second and third elements, respectively.
    • p1->next=NULL
    • while (p3 != NULL) do
      • p2->next=p1
      • p1=p2
      • p2=p3
      • p3=p3->next

    • p2->next=p1
    • return p2 as the head of the reversed list


    This is a pseudo code, of course, as I'm less interested in the actual implementation, and more about the algorithm itself.
    I was wondering if there's a more elegant way of doing this, since this gets quite complicated considering the cases where the list has less than three elements in it.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,776
    You are not allowed to copy the linked list, but one thing you can do is to create a "new" linked list by changing the next pointers. So, you could find the tail of the linked list and the node before it (if it exists). You set the tail to be the head of a new linked list, then set the next pointer of the node before it to be a null pointer (if applicable), thereby shortening your original linked list. Repeat to find the tail of the shortened linked list and the node before it. You append the new tail to the new linked list, then set the next pointer of the node before it to be a null pointer, thereby shortening the shortened linked list. Repeat until the shortened linked list is empty.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,907
    I'll start with your original implementation. The cases for fewer than 3 elements are not complex, but rather fairly trivial. Draw it out on paper if you need to. The case for zero- and one-element lists is ridiculously easy. The case for a two-element list isn't that difficult (mine is 4 lines). All you would have to do is
    Code:
    if zero or one elements
        // super trivial
    else if two elements
        // less trivial, but still trivial
    else
        your algorithm
    Analyze your algorithm carefully, it may work for two-element lists, leaving you with only the trivial zero-/one-element list case. Again, draw it out on paper if you need to.

    There is a recursive solution which, while not the most elegant, took me 5 lines and used 1 temp variable. You can run into trouble with extremely large lists, however, as you may run out of stack space with all those recursive calls.

    Of course, as laserlight mentioned, you can create a "new" list. Her solution works, however, I find it easier to work from the head of the list. Sometimes, to find these types of solutions, it helps to think about this in a more abstract manner. Forget that you have to explicitly manipulate the next pointer of the nodes, and instead focus on operations that apply to the list regardless of implementation. For example, you can add nodes by prepending (add at beginning), appending (add at end) and inserting in the middle. Also, you can remove nodes from the beginning, middle and end. Now, what operations can you use to extract nodes from the old list, and insert them into the new list, such that your new list is the reversal of your old list.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Easy way: Learn about push and pop operations. Then it's just a matter of:

    While the list is not empty, pop an item, and push it onto a new list.
    Then point the old list back at the new reversed list.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    You could initialize p1 and p2, then update p3 in the loop:


    • p1 = root;
    • if(p1 == NULL) return p1;
    • p2 = p1->next;
    • if(p2 == NULL) return p1;
    • p1->next=NULL
    • while (NULL != (p3 = p2->next)) do
      • p2->next=p1
      • p1=p2
      • p2=p3

    • p2->next=p1
    • return p2 as the head of the reversed list
    Last edited by rcgldr; 09-12-2014 at 09:39 PM.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,776
    Quote Originally Posted by iMalc
    Easy way: Learn about push and pop operations. Then it's just a matter of:

    While the list is not empty, pop an item, and push it onto a new list.
    Then point the old list back at the new reversed list.
    I suggested this in post #2.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Printing a reverse linked list
    By Nyah Check in forum C Programming
    Replies: 10
    Last Post: 04-13-2012, 01:59 PM
  2. Replies: 26
    Last Post: 05-03-2011, 11:52 AM
  3. how to reverse items in linked list?
    By ilikeapplepie in forum C Programming
    Replies: 8
    Last Post: 04-09-2011, 11:15 PM
  4. Linked List(+reverse) trouble
    By killmequick in forum C Programming
    Replies: 8
    Last Post: 09-18-2008, 01:40 PM
  5. reverse a singly linked list
    By ivandn in forum C Programming
    Replies: 15
    Last Post: 12-18-2001, 05:33 PM