单链表操作

声明单链表

class Node {  
    public int value;  
    public Node next;  
    public Node() {  
        value = -1;  
        next = null;  
    }  
    public Node(int i) {  
        value = i;  
        next = null;  
    }

建立单链表

/* 
 * 定义一个链表主类，并且定义各种对链表操作的方法 
 */  
public class Linklist {  
      
         public LNode head;//定义一个头结点  
  
/* 
 * 定义一个创建链表的方法 
 * 该方法称之为 ：尾插法：新产生的节点从尾部插入链表 
 */  
         public void createlink(int [] a){  
           LNode pnew;//定义pnew表示新产生的结点  
           LNode ptail=new LNode();//为尾节点分配堆内存  
           head=ptail;//初始时是头结点与尾节点相等  
           for(int i=0;i<a.length;i++){  
           pnew=new LNode();//为新产生的节点分配堆内存  
           pnew.setData(a[i]);//传递data值  
           ptail.setNext(pnew);//把新产生的节点设置为ptail的后继节点  
           pnew.setNext(null);//把新产生的节点的后继节点设为空  
           ptail=pnew;//移动 ptail节点的位置使之一直指向尾部  
           }  
         }

/* 
 * 定义判断链表中元素是否存在的方法 
 */  
         public void seachlink(int value){  
             LNode ptr;  
              ptr=head.getNext();  
              while(ptr!=null){//在节点非空的情况下寻找匹配的的值  
               if(value==ptr.getData()){//匹配成功是  
                System.out.println("找到数据:"+ptr.getData());  
                break;//退出循环  
               }  
               else{//当当前值不是要查找的值时，查找下一个  
                ptr=ptr.getNext();  
               }   
              }  
              if(ptr==null)//链表遍历完毕，没有找到时  
               System.out.println("链表中没有要查找数据");  
             }  
/* 
 * 定义一个删除节点的方法 
 */  
         public void deletelink(int value){  
              LNode ptr;  
              LNode p;  
              p=head;  
              ptr=head.getNext();  
              while(ptr!=null){  
               if(value==ptr.getData()){//判断链表中的当前值是否是要删除的节点  
                p.setNext(ptr.getNext());//把ptr的后继节点设置为p的后继节点，即在形式上在链表中删除了ptr节点  
               // System.gc();  
                System.out.println("删除数据"+value+"成功！");  
                break;  
               }  
               else{  
                p=ptr;//p指向ptr位置  
                ptr=ptr.getNext();//ptr指向其直接后继位置  
               }  
              }  
              if(ptr==null)  
               System.out.println("链表中没有要删除的数据！");  
             }  
/* 
 * 定义插入节点的方法 
 */  
     public void insertlink(int pos,int value){//两个参数，一个表示插入的位置，另一个表示插入的值  
              LNode ptr;  
              LNode pnew;//实例化新节点  
              ptr=head.getNext();  
              while(ptr!=null){  
               if(pos==ptr.getData()){  
                pnew=new LNode();  
                pnew.setData(value);  
                pnew.setNext(ptr.getNext());  
                ptr.setNext(pnew);//  
                System.out.println("插入数据"+value+"成功！");  
                break;  
               }  
               else{  
                ptr=ptr.getNext();  
               }  
              }  
              if(ptr==null)  
               System.out.println("插入数据失败！");  
             }  
  
           
           
/* 
 * 定义一个输出链表内容方法 
 */  
         public void printlink(){  
          LNode ptr;//实例化一个节点  
          ptr=head.getNext();//该节点取得头结点的后继节点  
          while(ptr!=null){  
           System.out.print(ptr.getData()+"->");  
           ptr=ptr.getNext();  
          }  
          System.out.println(" NULL");  
         }  
          
/* 
 * 下面给出一个测试用例，用数组创建一个整型的链表，并且把它输出         
 */  
     public static void main(String args[]){  
       int a[]=new int [10];  
       for(int i=0;i<a.length;i++){  
       a[i]=i;  
       }  
       Linklist list=new Linklist();  
       list.createlink(a);  
       System.out.println(" 链表输出如下：");  
       list.printlink();  
       System.out.println(" 插入元素后链表的输出如下：");  
       list.printlink();  
         
       }  
}

单链表逆序

package com.java.duncan;  
class Node {  
    public int value;  
    public Node next;  
    public Node() {  
        value = -1;  
        next = null;  
    }  
    public Node(int i) {  
        value = i;  
        next = null;  
    }  
    public void add(Node head, Node add) {  
        Node p = head;  
        if(p == null) return;  
        while(p.next != null) {  
            p = p.next;  
        }  
        p.next = add;  
    }  
    public void print(Node head) {  
        Node p = head;  
        if(p == null) System.out.println("链表为空！");  
        while(p != null) {  
            System.out.print(p.value + " ");  
            p = p.next;  
        }  
    }  
    public void reversePrint(Node node) {  
        if(node.next != null) {  
            reversePrint(node.next);  
            System.out.print(node.value + " ");  
        }  
    }  
      
    public Node Reverse(Node head) {  
        if(head==null || head.next==null) return head;  
        Node p1 = head;  
        Node p2 = head.next;  
        Node p3 = p2.next;  
        p1.next = null;  
        while(p3 != null) {  
            p2.next = p1;  
            p1 = p2;  
            p2 = p3;  
            p3 = p3.next;  
        }  
        p2.next = p1;  
        return p2;  
    }  
}  
  
public class ReverseList {  
    public static void main(String[] args) {  
        Node head = new Node();  
        for(int i = 1; i <= 10; i++) {  
            head.add(head,new Node(i));  
        }  
        head.print(head.Reverse(head));  
        //System.out.println();  
        //head.reversePrint(head);  
          
    }  
}

单链表查环

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast;
        ListNode slow;
        fast=slow=head;
        if(head==null||head.next==null)
            return false;
        while(fast.next!=null&&slow.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next; 
            if(fast==null)
            return false;
            if(fast==slow)
            {
                return true;
            }
        }
        return false;
    }
}