几个链表相关问题

 

一、约瑟夫环问题

已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。例如：n = 9,k = 1,m = 5

      主要思路：构建一个list，将n个人放入list中，规定开始位置k，开始遍历，每执行m次，将当前元素移除list，递归循环执行，直到list.size为零。以下为主要的两个方法的代码：

public static void process(int n,int k,int m) {
      // 构建一个list，存放人数
            LinkedList<Integer> list = new LinkedList<Integer>();
            for (int i = 0; i < n; i++) {
               if (i + k > n) {
               list.add(i + k - n);
          } else {
            list.add(i + k);
  }
}
      int count = 1;// 记录数的人数
      CycleRemove(list,count,m);
}

 

      public static void CycleRemove(LinkedList<Integer> list,int count,int m) {
            int len = list.size();
            if (len > 1) {
               for (int i = 0; i < len; i++) {
               if (count == m) {// 第m个时，remove
                  removedStr.append(list.get(i)).append(",");
                  list.remove(i);
                  len = list.size();
                  i--;
                  count = 0;
}
                  count++;
}
                  CycleRemove(list,count,m);
} else {
                  if (len != 0) {
                  removedStr.append(list.get(0)).append(",");
   }
  }
 }

 二、单链表排序

主要思路：比较每两个相邻值得大小，list排序

 

public static void main(String []args)  
   {  
        Comp c1 = new Comp(3,3);  
        Comp c2 = new Comp(1,1);  
        Comp c3 = new Comp(5,3);  
        Comp c4 = new Comp(4,3);  
          
        TreeSet<Comp>treeSet1 = new TreeSet<Comp>();     
        for (Comp comp : treeSet1) {  
            System.out.println(comp);  
        }  
          
        ArrayList<Comp> list = new ArrayList<Comp>();  
        list.add(c1);  
        list.add(c2);  
        list.add(c3);  
        list.add(c4);  
        Collections.sort(list);  
        for (Comp comp : list) {  
            System.out.println(comp);  
        }  
         
   }  

  三、判断单链表是否有环

主要思路：给定起始位置，给每个结点标记，给定两个结点NodeA，NodeB，每循环一次NodeA前进两个结点，NodeB前进一个结点，若有环，必相遇，即结点标记相同。

public class CircleJudge {
//	给定一个单链表，试判断该单链表有无存在环。
//	算法的思想是设定两个指针p, q，其中p每次向前移动一步，q每次向前移动两步。
//	那么如果单链表存在环，则p和q相遇；否则q将首先遇到null。
	
	ListNode root = new ListNode("root");
	public static void main(String arg []){
		CircleJudge cj = new CircleJudge();
		cj.CreateList();
	}
	//建立长度为10的链表，前一个结点指向下一结点，形成一个闭环
	public void CreateList(){
		ListNode  Node[] =new ListNode[10];
        Node[0] = root;
		for(int i = 1;i<Node.length;i++){
			Node[i] = new ListNode("Node"+i);
			Node[i-1].next = Node[i] ;
	} 
		Node[9].next = root;
		circle();
	}
	
	//建立两个结点分别每次前进一步和两步，若相遇则输出链表有环
	public void circle(){
		ListNode NodeA = root;
		ListNode NodeB = root; 
		while(true){
			NodeA = NodeA.next;
			NodeB = NodeB.next.next;
			if(NodeA.str.equals(NodeB.str)){
				System.out.println("该链表有环，程序结束");
				break;
			}
		}
	}
	
	//匿名内部结点类
	class ListNode {
	     //定义数据和指针属性，str用于标记结点验证结点是否相同，next为指针
		public String str;
		public ListNode next;
		
		//构造方法
		public ListNode(String str){
			this.str=str;
		}
	}
}