链表知识点总结

清疚 2022-05-26 05:56 150阅读 0赞

package 链表;

//定义一个结点  
class Node\{  
    Node next = null;  
    int data;  
    public Node(int data)\{  
        this.data = data;  
    \}  
\}

public class MyLinkedList \{  
    Node head = null;//链表的头结点  
      
    //添加结点  
    public void addNode(int data)\{  
        //将数据封装到结点中，即创建新结点  
        Node node = new Node(data);  
        //如果链表是空链表，将新结点添加给头结点  
        if(head == null)\{  
            head = null;  
            return;  
        \}  
        //如果链表是非空链表，将新节点添加到链表末尾处  
        Node tmp = head;  
        while(tmp.next!=null)\{  
            tmp = tmp.next;  
        \}  
          
        tmp.next = node;  
    \}  
      
    //删除结点  
    public boolean delNode(int index)\{  
        //角标不合理  
        if(index<1 || index>length())\{  
            return false;  
        \}  
          
        //特殊情况，index==1  
        if(index == 1)\{  
            head = head.next;  
            return true;  
        \}  
        //index大于等于2的情况  
        int i =2;  
        Node preNode = head;  
        Node curNode = preNode.next;  
        while(curNode!=null)\{  
            if(index == i)\{  
                preNode.next = curNode.next;  
                return true;  
            \}  
            preNode = curNode;  
            curNode = curNode.next;  
            i++;  
        \}  
        return true;  
    \}  
      
    /\*\*  
     \* 对链表进行排序  
     \* 思路：用选择排序的思想对链表进行排序。第一个结点和第二个结点相比较，小的往前放；  
     \* 第一个结点和第三个结点相比较，小的往前放...第一次排序后，最小值放在第一个结点处。  
     \* 将第一个结点的下一个结点重新设为第一个结点，重复上述过程  
     \*/  
    public Node orderList(Node head)\{  
        Node curNode = head;  
          
        while(curNode.next!=null)\{  
            Node nextNode = curNode.next;  
              
            while(nextNode!=null)\{  
                if(curNode.data>nextNode.data)\{  
                    int tmp = curNode.data;  
                    curNode.data = nextNode.data;  
                    nextNode.data = tmp;  
                \}  
                  
                nextNode = nextNode.next;  
            \}  
              
            curNode = curNode.next;  
        \}  
          
        return head;  
    \}  
      
    /\*\*  
     \* 反转链表  
     \*   
     \* 思路：从头到尾遍历链表。在断开当前结点与下一个结点之间的联系之前，先将下一个  
     \* 结点保存，然后，让当前结点指向上一个结点，将当前结点定义为新的上一个结点，将  
     \* 当前结点的下一个结点定义为新的当前结点。直到当前结点的下一个结点为null，将  
     \* 当前结点定义为反转后的头结点。  
     \*/  
    public Node reverseList(Node head)\{  
        if(head == null)\{  
            return null;  
        \}  
          
        Node currentNode = head;//定义当前结点，初始值为头结点  
        Node preNode = null;//定义当前结点的上一个结点，初始值为null  
        Node reverseHead = head;//定义反转后链表的头结点，初始值为head  
        while(currentNode != null)\{  
            Node aftNode = currentNode.next;//保存当前结点的下一个结点  
              
            //如果当前结点为尾结点，当前结点即为反转后链表的头结点  
            if(currentNode.next == null)\{  
                reverseHead = currentNode;  
            \}  
            currentNode.next = preNode;//断开当前结点与下一个结点的联系，并指向上一个结点  
            preNode = currentNode;//将当前结点定义为新的上一个结点  
            currentNode = aftNode;//将当前结点的下一个结点定义为新的当前结点  
        \}  
          
        return reverseHead;  
    \}  
      
    /\*\*  
     \* 求链表中倒数第k个结点  
     \*   
     \* 思路：在查找过程中，设置两个指针，让其中一个指针比另一个指针先前移k-1步，然后  
     \* 两个指针同时往前移动。循环直到先行指针指向尾结点时，另一个指针所指的位置就是所  
     \* 要找的位置。  
     \*   
     \* @param head  
     \* @param k  
     \* @return  
     \*/  
    public Node findElem(Node head,int k)\{  
        //判断k是否合理  
        if(k<1 && k>length())\{  
            return null;  
        \}  
          
        //定义两个指针，p1和p2  
        Node p1 = head;  
        Node p2 = head;  
          
        //让p1指针先前移k-1步  
        for(int i=0;i<k-1&&p1!=null;i++)  
            p1 = p1.next;  
          
        if(p1 == null)\{  
            System.out.println("k不合法");  
            return null;  
        \}  
          
        //两个指针同时向前移动，当先行指针指向尾结点时，另一个指针所指的位置就是所要找的位置  
        while(p1.next != null)\{  
            p1 = p1.next;  
            p2 = p2.next;  
        \}  
          
        return p2;  
    \}  
      
    /\*\*  
     \* 如何判断两个链表是否相交  
     \*   
     \* 思路：如果两个链表相交，那么它们一定有着相同的尾结点，因此实现思路为，分别遍历  
     \* 两个链表，记录它们的尾结点，如果它们的尾结点相同，那么说明这两个链表相交，否则  
     \* 不相交。  
     \*   
     \* @param head1  
     \* @param head2  
     \* @return  
     \*/  
    public boolean isIntersect(Node head1,Node head2)\{  
        if(head1==null || head2==null)\{  
            return false;  
        \}  
          
        //找出第一个链表的尾结点  
        Node tail1 = head1;  
        while(tail1.next != null)\{  
            tail1 = tail1.next;  
        \}  
        //找出第二个链表的尾结点  
        Node tail2 = head2;  
        while(tail2.next != null)\{  
            tail2 = tail2.next;  
        \}  
          
        return tail1 == tail2;  
    \}  
      
    /\*\*  
     \* 如何检测一个单链表是否有环  
     \*   
     \* 思路：定义两个指针fast和slow，快指针一次走两步，慢指针一次走一步，快指针每移动  
     \* 一次都要根慢指针比较，直到当快指针等于慢指针时，说明这个链表是带环的单向链表，否则  
     \* 说明这个链表不是带环的单向链表。  
     \*   
     \* @param head  
     \* @return  
     \*/  
    public boolean hasCycle(Node head)\{  
        if(head == null)\{  
            return false;  
        \}  
          
        Node fast = head;  
        Node slow = head;  
        while(fast!=null&&fast.next!=null)\{  
            slow = slow.next;  
            fast = fast.next.next;  
            if(slow == fast)\{  
                return true;  
            \}  
        \}  
        return false;  
    \}  
      
    //计算链表长度  
    public int length()\{  
        Node tmp = head;  
        int length = 0;  
        while(tmp!=null)\{  
            length++;  
            tmp = tmp.next;  
        \}  
        return length;  
    \}  
      
    //打印链表  
    public void printList()\{  
        Node tmp = head;  
        while(tmp!=null)\{  
            System.out.println(tmp.data);  
            tmp = tmp.next;  
        \}  
    \}  
\}