Java单链表接本操作

一时失言乱红尘 2022-09-25 06:13 203阅读 0赞

Java单链表基本操作：  
（一）顺序查找；  
（二）指定位置增加节点；  
（三）删除当前节点；  
（四）单链表反转；  
（五）输出倒数第K个节点；  
（六）删除重复节点；  
（七）排序  
（八）合并两个排序单链表；  
（九）交换相邻节点的值；  
（十）O（n）时间内查找单链表的中间节点  
（十一）逆序（从尾至头）输出单链表  
（十二）判断单链表是否有环  
（十三）判断两个链表是否相交  
（十四）已知一个单链表中存在环，求进入环中的第一个节

## 定义node： ##

public class Node {
        int data;
        Node next;
        Node(int data){
            this.data=data;
        }
    }

## 定义ListNode： ##

public class ListNode {
        public static Node getSingleList(){
            Node head=new Node(3);
            Node node1=new Node(6);
            Node node2=new Node(8);
            Node node3=new Node(6);
            Node node4=new Node(2);
            head.next=node1;
            node1.next=node2;
            node2.next=node3;
            node3.next=node4;
            node4.next=null;
            return head;
        }
    
        public static void printList(Node node){
            System.out.print("List:");
            while(node!=null){
                System.out.print(node.data+"-->");
                node=node.next;
            }
            System.out.println();
        }
    }

## （一）顺序查找 ##

/*
     * 查找值为num的元素位置，没有返回-1*/
    public class SeqSearch {
    
        public static void main(String[] args) {
            Node head=ListNode.getSingleList();
            ListNode.printList(head);
            int num=9;
            int id=new SeqSearch().searchNumId(head,num);
            System.out.println("要查找的元素位置为："+id);
        }
        public int searchNumId(Node head,int num){
            int id=1;
            while(head!=null&&head.data!=num){
                head=head.next;
                id++;
            } 
            if(head==null) id=-1;
            return id;
        }
    }

## （二）指定位置增加节点 ##

/*
     * 将新节点增加在指定位置*/
    public class AddNode {
    
        public static void main(String[] args) {
            Node head=ListNode.getSingleList();
            ListNode.printList(head);
            Node add=new Node(0);
            int id=0;
            head=new AddNode().addNode(head,add,id);
            ListNode.printList(head);
        }
        public Node addNode(Node head,Node add,int id){
            if(id==0) {
                add.next=head;
                head=add;
            }else{
                while(head.next!=null&&id>1){
       //寻找节点增加的位置
                    head=head.next;
                    id--;
                }
                add.next=head.next;
                head.next=add;
            }
            return head;
        }
    }

## （三）删除当前节点 ##

单链表中要删除当前节点，如果当前节点不是头节点，则无法使前面的节点直接指向后面的节点，这时候我们可以换一种思路，即：将当前节点的下一节点值附给当前节点，然后删除当前节点的下一节点，这样就等效为删除当前接节点了。

/**
     * Definition for singly-linked list.
     * public class Node {
     *     int data;
     *     Node next;
     *     Node(int x) { data = x; }
     * }
     */
    
        public void deleteNode(Node node) {
            node.val=node.next.val;
            node.next=node.next.next;
        }

## （四）单链表反转 ##

可以参考[http://blog.csdn.net/u010305706/article/details/50810005][http_blog.csdn.net_u010305706_article_details_50810005]  
表示更详细

public class ReverseSingleList {
        public static void main(String args[]){
            Node head=ListNode.getSingleList();
            ListNode.printList(head);
            head=new ReverseSingleList().reverseSingleList(head);
            ListNode.printList(head);
        }
         public Node reverseSingleList(Node head){
                if(head== null||head. next== null){
                     return head;
               }
               Node preNode=head;
               Node pNode=head. next;
               Node markNode=head. next;
               head. next= null; //一定要断开head节点的next节点，不然形成了循环
                while(markNode!= null){
                    markNode=markNode. next;
                    pNode. next= preNode;
                     preNode=pNode;
                    pNode=markNode;
               }
                return preNode;
         }
    }

## （五）查找倒数第K个节点 ##

package listnode;
    
    public class LastKNode {
    
        public static void main(String[] args) {
            Node head=ListNode.getSingleList();
            ListNode.printList(head);
            int k=3;
            head=new LastKNode().getLastKNode(head,k);
            System.out.println(head.data);
    
        }
        public Node getLastKNode(Node head, int k){
            Node node=head;
            while(node. next!= null&&k>0){
                node=node. next;
                k--;
           }
           while(node!= null){
           node=node. next;
           head=head. next;
           }
           return head;
        }
    }

## （六）删除重复节点 ##

package listnode;
    
    public class DeleteDuplecate_SingleList {
        public static void main(String[] args) {
            Node head=ListNode.getSingleList();
            ListNode.printList(head);
            deleteNode(head);
            ListNode.printList(head);
        }
    
        public static void deleteNode(Node head){
            while(head.next!=null){
                Node p=head;
                while(p.next!=null){
                    if(p.next.data==head.data){
                        p.next=p.next.next;
                    }
                    p=p.next;
                }
                head=head.next;
            }
        }
    }

## （七）排序 ##

单链表的插入排序比数组麻烦，因为每次都都要从头节点开始往后遍历，头节点也需要单独处理

package listnode;
    
    public class SortList {
        public static void main(String[] args) {
            Node head=ListNode.getSingleList();
            ListNode.printList(head);
            head=new SortList().insertSortList(head);
            ListNode.printList(head);
        }
    
        public Node insertSortList(Node head){
            Node p=head.next;
            Node pre=head;
            while(p!=null){
                Node cur=head;  //比较节点，每次都是从头节点开始
                Node q=p.next;
                if(p.data<head.data){ //由于是单链表，每次只能从头节点开始比较
                    pre.next=q;
                    p.next=head;
                    head=p;
                }else
                    while(cur.next!=p){
                        if(p.data<cur.next.data){
       //将P与cur.next进行比较，方便单链表插入
                            pre.next=q;
                            p.next=cur.next;
                            cur.next=p;
                            p=pre;  //保证pre每次指向的都是p前面的一个节点
                        }else
                            cur=cur.next;
                    }
                pre=p;
                p=q;
            }
            return head;
        }
    }

## （八）合并两个有序单链表 ##

package listnode;
    
    public class MergeSeqList {
        public static void main(String[] args) {
            Node head1=SortList.insertSortList(ListNode.getSingleList());
            Node head2=SortList.insertSortList(ListNode.getSingleList());
            head1=new MergeSeqList().mergeTwoLists(head1, head2);
            ListNode.printList(head1);
    
        }
    
        public Node mergeTwoLists(Node l1, Node l2) {
            Node head=null;
                  if(l1==null){
       //先判断两个链表是否为空
                         return l2;
                  }
                  if(l2==null){
                         return l1;
                  }
                  if(l1.data<=l2.data){
                         head=l1;
                         l1=l1.next;
                  }else{
                         head=l2;
                         l2=l2.next;
                  }
                  Node temp=head;
                  while(l1!=null&&l2!=null){
                         if(l1.data<=l2.data){
                                temp.next=l1;
                                l1=l1.next;
                         }else{
                                temp.next=l2;
                                l2=l2.next;
                         }
                         temp=temp.next;
                  }
                  if(l1!=null){
                         temp.next=l1;
                  }
                  if(l2!=null){
                         temp.next=l2;
                  }
                  return head;
        }
    }

## （九）交换相邻节点对的值 ##

本题目来源于：Leetcode:  
24.swap nodes in pairs(单链表中交换节点对的值)  
Given a linked list, swap every two adjacent nodes and return its head.  
For example,  
Given 1->2->3->4, you should return the list as 2->1->4->3.  
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.  
有两种思路解决本题：  
（1）利用链表的特点，改变链表指针的指向，改变了节点的位置

package listnode;
    
    public class SwapPairs {
    
        public static void main(String[] args) {
            Node head=ListNode.getSingleList();
            ListNode.printList(head);
            head=new SwapPairs().swapPairs(head);
            ListNode.printList(head);
        }
    
        public Node swapPairs(Node head) {
            Node root=head;
               if(head!=null&&head.next!=null){
                      root=head.next;
                      Node pre=head;
                      Node p=null;
                      Node q=null;
                      while(head!=null&&head.next!=null){
    
                             p=head.next;
                             q=p.next;
    
                             pre.next=p;
                             p.next=head;
                             head.next=q;
    
                             pre=head;
                             head=q;
                      }
               }
               return root;
        }
    }

（2）改变相邻节点对的值，不改变节点指针（通过数组思维实现）

public ListNode swapPairs(ListNode head){
           public ListNode swapPairs(ListNode head) {
            ListNode p=head;
            while(p!=null){
                ListNode q=p.next;
                if(q!=null){
                    int temp=p.val;
                    p.val=q.val;
                    q.val=temp;
                    p=p.next;
                }
                p=p.next;
            }
            return head;
        }
    }

## （十）判断是否有环并输出环长度以及环的入口节点 ##

本文解决三个问题：

1.单链表是否有环？  
2.有则输出环的长度？  
3.找到环的入口节点？

分析：  
定义两个指针fast 和slow，fast每次向后移动两个节点，slow每次想后移动一个节点。  
1.如果没有环，则fast首先到达链表结尾；  
2.链表有环的情况下：fast与slow两次相遇，slow中间走过的节点处即为环的长度；  
3.找环的入口节点稍微复杂点，有如下的推导过程：

相遇的时候，slow共移动了s步，fast共移动了2s步。  
定义a如下： 链表头移动a步到达入口点。  
定义x如下： 入口点移动x步到达相遇点。  
定义r如下： 环的长度。  
定义L如下： 链表总长度为L。

其中Ｌ　＝　a + r

那么slow和fast相遇了，fast必然比slow多走了n个圈，也就是 n\*r 步，那么  
s = a + x  
2s = s + n\*r ， 可得 s = n\*r  
将s=a+x，带入s =n\*r，可得 a+x = n\*r, 也就是 a+x = (n-1)\*r + r 　　  
从表头移动到入口点，再从入口点移动到相遇点，也就是移动了整个链表的距离，即是 L = a + r , 所以r = L - a  
所以 a+x = (n-1)\*r + L - a , 于是 a = (n-1)\*r + L - a - x  
得到：从表头到入口点的距离，等于从相遇点到入口点的距离。  
所以，从表头设立一个指针，从相遇点设立一个指针，两个同时移动，必然能够在入口点相遇，这样，就求出了相遇点。

上面三个问题的java解决代码：

方法一：一次性求解

public class ExistCircle {
        static int id = 1;
        public Node existCircle(Node head){
            Node fast = head;
            Node slow = head;
            while(fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
    
                //输出环长
                while(fast == slow) {
                    int len = 1;
                    fast = fast.next.next;
                    slow = slow.next;
                    while (fast != slow) {
                        len++;
                        fast = fast.next.next;
                        slow = slow.next;
                    }
                    System.out.println("The length of circle is:" + len);
    
                    //输出环入口节点
                    fast = head;
                    while (fast != slow) {
                        fast = fast.next;
                        slow = slow.next;
                        id++;
                    }
                    return slow;
                }
            }
            return null;
        }
        public static void main(String[] args) {
            Node head=new Node(3);
            Node node1=new Node(6);
            Node node2=new Node(8);
            Node node3=new Node(5);
            Node node4=new Node(2);
            Node node5=new Node(7);
            head.next=node1;
            node1.next=node2;
            node2.next=node3;
            node3.next=node4;
            node4.next=node5;
            node5.next=node3;
            Node port = new ExistCircle().existCircle(head);
            System.out.println("环入口为第" + id + "个节点:" + port.data);
        }
    }

方法二:分开求解：

package listnode;
    
    public class ExitCircle {
        static int id = 1;
    
        public static void main(String[] args) {
            //测试
            Node head=new Node(3);
            Node node1=new Node(6);
            Node node2=new Node(8);
            Node node3=new Node(5);
            Node node4=new Node(2);
            Node node5=new Node(7);
            head.next=node1;
            node1.next=node2;
            node2.next=node3;
            node3.next=node4;
            node4.next=node5;
            node5.next=node3;
            new ExitCircle().exitCircle(head);
    
            Node port = new ExitCircle().findLoopPort(head);
            System.out.println("环入口为第" + id + "个节点:" + port.data);
    
        }
        //环入口节点
        //环的入口节点到快慢指针相遇的距离 与 链表头节点到环入口节点的距离相等
        public Node findLoopPort(Node head){
            Node slow = head, fast = head;
            while(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast){
                    fast = head;
                    while(head != slow){
                        id++;
                        head = head.next;
                        slow = slow.next;
                    }
                    return slow;
                }
            }
            System.out.print("NoLoop !");
            return null;
        }
    
        public boolean exitCircle(Node head){
            Node fast = head;
            Node slow = head;
            while(fast != null && fast.next != null){
       //判断是否由环，注意fast.next = null的情况
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow){
       //存在环
                    int count = 0;
                    while(true){
                        count ++;
                        fast = fast.next.next;
                        slow = slow.next;
    
                        if(fast == slow){
       //快慢指针在第二次相遇，这个点肯定是第一次相遇的点 
                            System.out.println("环的长度：" + count);
                            return true;
                        }
                    }
                }
            }
            System.out.println("false!");
            return false;
        }
    
    }

[http_blog.csdn.net_u010305706_article_details_50810005]: http://blog.csdn.net/u010305706/article/details/50810005