Monday, December 12, 2011

Linked List Manipulation for 2 Lists

Write functions for following operations on TWO sorted singly Linked Lists

1.SortedMerge()---Both Iterative and recursive
Variation 1:
Takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order.SortedMerge() should return the new list.No additional nodes must be used.
Variation 2:
Given 2 sorted linked lists - merge them. Make sure you don't have duplicates in the merged list. The input lists could have duplicates within them or across the 2 lists.

2.SortedIntersect()---
Two lists sorted in increasing order, create and return a new list representing the intersection of the two sorted lists. The new list should be made with its own memory — the original lists should not be changed.

Merge 2 Sorted Lists
http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/
http://www.geeksforgeeks.org/in-place-merge-two-linked-list-without-changing-links-of-first-list/
http://algorithms.tutorialhorizon.com/merge-or-combine-two-sorted-linked-lists/

Merge k Sorted Lists
http://www.geeksforgeeks.org/merge-k-sorted-linked-lists

Merge two sorted linked lists such that merged list is in reverse order
http://www.geeksforgeeks.org/merge-two-sorted-linked-lists-such-that-merged-list-is-in-reverse-order/

3.ShuffleMerge()
Given two lists, merge their nodes together to make one list, taking nodes alternately
between the two lists. So ShuffleMerge() with {1, 2, 3} and {7, 13, 1} should yield {1, 7,2, 13, 3, 1}. If either list runs out, all the nodes should be taken from the other list.
http://algorithms.tutorialhorizon.com/merge-a-linked-list-into-another-linked-list-at-alternate-positions/

4.Write Functions for following operations on two Singly Linked Lists
1. MoveNode()---Takes two lists, removes the front node from the second list and pushes it onto the front of the first

2..Append()--- Takes two lists, 'a' and 'b', appends 'b' onto the end of 'a',and then sets 'b' to NULL (since it is now trailing off the end of 'a').


No comments:

Post a Comment