CODEWITHSUNDEEP
algorithmdata-structureslinked-list
codewarrior
codewarrior

Reputation: 1034

Reverse and merge a linked list

Problem: Given a sorted linked list

1->2->3->4->5->6->7

change the pointers in the linked list to make it

7->1->6->2->5->3->4

using constant space.

I tried to solve it using the following algorithm:

  1. Find the middle node of the linked list using 2 nodes, a fast node and a slow node.

  2. Reverse the linked list from the middle node. Mark the middle node as y and start node as x.

    1->2->3->7->6->5->4
x        y

  3. If y=middle node AND y!= x.next, then swap y and x.next. Then swap x and x.next.

    1->7->3->2->6->5->4
x        y
7->1->3->2->6->5->4
x        y

    Advance x by two nodes and y by 1 node.

    7->1->3->2->6->5->4
      x     y

  4. Now if (x != y) { swap x and y }

    7->1->6->2->3->5->4
      x     y

  5. Advance x by two nodes and y by 1 node

    7->1->3->2->6->5->4
            x  y
  6. Repeat steps 4 and 5 till y becomes null (reaches end of linked list) or x == y

So finally we get 

7->1->6->2->5->3->4

Question:

Is there a simpler way to do this?

Upvotes: 1

Views: 772

Answers (2)

Анатолий
Анатолий

Reputation: 2857

This is simple solution:

  1. Found list size.
  2. Spilt by 2 same lists.
  3. Reverse second part.
  4. Merge lists.

Sample:

  1. 1->2->3->4->5->6->7 size is 7. (We should split by 4 and 3)
  2. Split by 1->2->3->4 and 5->6->7
  3. Reverse second part 1->2->3->4 and 7->6->5
  4. Merge: 7->1->6->2->5->3->4

Upvotes: 2

iampat
iampat

Reputation: 1101

You can find two sophisticated solutions in Linked list problem problem 17 and 18.

Upvotes: 0

Related Questions