ID #5716

合并有序链表

场景:存在表L1(A B C D E),有序表L2(2 4 8),有序表L3(2 5).删除表L1中位 置序号属于有序表L2和L3,即删除后L1(A C).

使用的数据结构是一个链表节点

public class Inode {
  private int value;
  private Inode next;
  public Inode(int value) {
    this.value = value;
    next = null;
  }
  public Inode(int value, Inode next) {
    this.value = value;
    this.next = next;
  }
  public int getValue() {
    return value;
  }
  public void setValue(int value) {
    this.value = value;
  }
  public Inode getNext() {
    return next;
  }
  public void setNext(Inode next) {
    this.next = next;
  }
}

具体实现如下.

1.方法getSeqList(IntLinkedList l1, IntLinkedList l2,int targetSize) 将合并两个有序表为一个有序表,并且为截尾,所由大于targetSize(大于要处理 链表长度)的数字将不予考虑;

2.方法removeSeqs(IntLinkedList seqList)依据seqList的数值,对当前链表 进行删除操作,只作一次循环操作,所以每删除一个节点,需要将seqList中的所有 值向前移一位(具体实现为每次减去一个整型值turn);

public class IntLinkedList {
  private Inode head, tail;
  private int size;
  public IntLinkedList() {
   head = tail = null;
   size = 0;
  }
  public IntLinkedList(Inode node) {
   head = tail = node;
   size = 1;
  }
  public int getSize() {
   return size;
  }
  public boolean isEmpty() {
   return size <= 0;
  }
  public void insertLast(int value) {
   if (value <= 0)
     throw new UnsupportedOperationException("Below Zero");
   Inode node = new Inode(value);
   if (size == 0)
     head = tail = node;
   else {
     tail.setNext(node);
     tail = node;
   }
   size++;
  }
  public int removeFirst() {
   if (size == 0)
     throw new UnsupportedOperationException("List empty");
   Inode node = head;
   head = head.getNext();
   size--;
   node.setNext(null);
   return node.getValue();
  }
  public void removeSeqs(IntLinkedList seqList) {
   int turn = 0;
   while (seqList.isEmpty() == false) {
      Inode node = head;
      Inode prev = null;
      int seq = seqList.removeFirst() - 1 - turn;
     while (seq > 0) {
       prev = node;
       node = node.getNext();
       seq--;
     }
     prev.setNext(node.getNext());
     node.setNext(null);
     turn++;
    }
  }
  public static IntLinkedList getSeqList(IntLinkedList l1, IntLinkedList l2, int targetSize) {
   IntLinkedList seqList = new IntLinkedList();
   int seq1 = targetSize + 1, seq2 = targetSize + 1;
   boolean use1 = false, use2 = false;
   if (!l1.isEmpty())
      seq1 = l1.removeFirst();
   if (!l2.isEmpty())
      seq2 = l2.removeFirst();
   if (seq1 <= targetSize && seq1 > 0)
     use1 = true;
   if (seq2 <= targetSize && seq2 > 0)
     use2 = true;
   while (use1 && use2) {
    if (seq1 - seq2 > 0) {
      seqList.insertLast(seq2);
      use2 = false;
      seq2 = targetSize + 1;
      if (!l2.isEmpty())
      seq2 = l2.removeFirst();
     if (seq2 <= targetSize)
      use2 = true;
    } else if (seq1 - seq2 == 0) {
     seqList.insertLast(seq2);
      use1 = use2 = false;
      seq1 = targetSize + 1;
      seq2 = targetSize + 1;
     if (!l1.isEmpty())
      seq1 = l1.removeFirst();
     if (!l2.isEmpty())
       seq2 = l2.removeFirst();
     if (seq1 <= targetSize)
      use1 = true;
     if (seq2 <= targetSize)
      use2 = true;
     } else {
     seqList.insertLast(seq1);
     use1 = false;
     seq1 = targetSize + 1;
     if (!l1.isEmpty())
      seq1 = l1.removeFirst();
     if (seq1 <= targetSize)
       use1 = true;
    }
   }
   while (use1) {
    seqList.insertLast(seq1);
    use1 = false;
    seq1 = targetSize + 1;
    if (!l1.isEmpty())
     seq1 = l1.removeFirst();
    if (seq1 <= targetSize)
     use1 = true;
   }
   while (use2) {
    seqList.insertLast(seq2);
    use2 = false;
    seq2 = targetSize + 1;
    if (!l2.isEmpty())
      seq2 = l2.removeFirst();
    if (seq2 <= targetSize)
      use2 = true;
   }
   return seqList;
  }
  public static void printAll(IntLinkedList l) {
   Inode node = l.head;
   while (node != null) {
     System.out.print((char) node.getValue() + " ");
     node = node.getNext();
   }
   System.out.println();
  }
  public static void printDebug(IntLinkedList l) {
   Inode node = l.head;
   while (node != null) {
     System.out.print(node.getValue() + " ");
     node = node.getNext();
   }
   System.out.println();
  }
  public static void main(String[] args) {
   IntLinkedList seq1 = new IntLinkedList();
   seq1.insertLast(2);
   seq1.insertLast(4);
   seq1.insertLast(8);
   IntLinkedList seq2 = new IntLinkedList();
   seq2.insertLast(2);
   seq2.insertLast(5);
   IntLinkedList charList = new IntLinkedList();
   charList.insertLast('A');
   charList.insertLast('B');
   charList.insertLast('C');
   charList.insertLast('D');
   charList.insertLast('E');
   printAll(charList);
   charList.removeSeqs(getSeqList(seq1, seq2, charList.getSize ()));
   printAll(charList);
  }
}


2011-07-01 18:29
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

根据Merge Sort原理,自己实现的归并排序算法+详细

常见排序算法的实现(六)-归并排序

二叉树遍历算法集合

[算法问题]合并两个已经排序的数组为另一个数组

一个简单有效的洗牌算法