/* * Copyright (C) 2009 E.Albert, P.Arenas, S.Genaim, G.Puebla, and D.Zanardini * https://costa.ls.fi.upm.es * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ package pubs; /** * This class implements several operations on singly linked lists * * @author E.Albert, P.Arenas, S.Genaim, and G.Puebla * */ public class MergeList { private int head; private MergeList tail; public MergeList(int head, MergeList tail) { this.head = head; this.tail = tail; } public MergeList append(MergeList other) { if (tail == null) return new MergeList(head,other); else return new MergeList(head,tail.append(other)); } public MergeList reverseAcc(MergeList acc) { if (tail == null) return new MergeList(head,acc); else return tail.reverseAcc(new MergeList(head,acc)); } public MergeList reverse() { if (tail == null) return this; else return tail.reverse().append(new MergeList(head,null)); } /** * Returns a sorted list which is the result of merging * the sorted list "this" with the sorted list other. * * @param other * @return */ public MergeList merge(MergeList other) { if (other == null) return this; else if (head <= other.head) if (tail != null) return new MergeList(head,tail.merge(other)); else return new MergeList(head,other); else return new MergeList(other.head,merge(other.tail)); } public static void main(String[] args) { // Prepare the test MergeList test = new MergeList(1,null); for (int i = 3; i <= 21; i = i + 2) { MergeList aux = new MergeList(i,null); test = test.append(aux); } MergeList other = new MergeList(2,null); for (int i = 4; i <= 22; i = i + 2) { MergeList aux = new MergeList(i,null); other = other.append(aux); } // Test MergeList result = test.merge(other); } }