首页 > 编程语言 > 详细

用java实现单链表的问题汇总

时间:2019-11-22 01:29:51      阅读:114      评论:0      收藏:0      [点我收藏+]

单链表的每个结点都包含有值,还包含链接下一结点的引用字段。链表将所有结点按顺序链接组织起来。以上为链表的基本定义,最近写了单链表的一些实现,也进行了一些思考,当然我的思考可能有所遗漏或者不对,写出来的代码健壮性可能不太好,如果有错误或更好的方法欢迎大家指正。先总结一下单链表,之后找个时间再总结一下双链表。

首先链表定义如下:

1 public class Node {
2 
3     Node next = null;
4     int val;
5     public Node(int x) {
6         val = x;
7     }
8 }

 

新建一个类,实现关于单链表的一些问题,首先定义了头变量

Node head = null;

 

实现链表的增加:关于链表的增加,其实可以汇总成一个方法,但是这里分为了从头、尾、和中段插入结点

//链表头部插入新节点
    public void addFirst(int value) {
        Node node = new Node(value);
        if(head != null) {
            node.next = head;
            head = node;
        }
        head = node;
    }
    //链表尾部插入新节点
    public void addLast(int value) {
        /*Node node = new Node(value);
        Node cur = head;
        if (head == null) {
            cur = node;
            return;
        }
        while(cur != null) {
            cur = cur.next;
        }
        cur.next = node;*/
        add(length(), value);
    }
    //链表的长度
    public int length() {
        int length = 0;
        Node cur = head;
        while(cur != null) {
            length++;
            cur = cur.next;
        }
        return length;
    }

    //链表中间插入
    public void add(int index,int value) {
        Node cur = head;
        if (index < 0 || index > length()) {
            throw new IllegalArgumentException("违法操作,索引不存在");
        }
        if (index == 0) {
            addFirst(value);
        }else {
            for (int i = 0; i < index-1 ;i++) {
                cur = cur.next;
            }
            Node node = new Node(value);
            node.next = cur.next;
            cur.next = node;
        }
    }

链表实现打印的功能,实际就是对链表进行遍历:

//链表打印
    public void printList() {
        Node cur = head;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }

 

链表的删除我写作了一个方法,根据索引去对某个结点进行删除操作

//链表删除
    public void delete(int index) {
        Node pre = head;
        
        if (index < 0 || index > length()) {
            throw new IllegalArgumentException("违法操作,索引不存在");
        }
        if (index == 0) {
            if(head != null) {
                head = head.next;
                return;
            }else {
                System.out.println("首节点为空");
            }
        }
        else {
            for(int i = 0; i < index -1; i++) {
                pre = pre.next;
            }
            pre.next = pre.next.next;
        }
    }

 

链表根据索引进行某个结点的查询,并返回某个结点的值

//链表根据索引查询返回值
    public int findNode(int index) {
        Node pre = head;
        
        if (index < 0 || index > length()) {
            throw new IllegalArgumentException("违法操作,索引不存在");
        }else {
            if (head == null) {
                return 0;
            }
            else {
                for (int i = 0 ;i < index ; i++) {
                    pre = pre.next;
                }
            }
        }
        return pre.val;
    }

 

查找倒数第n个结点,这里的思路是在单链表中定义两个指向头部的结点,比如a和b,让a结点先走n步,然后a、b同时开始遍历结点,当a走到为null时,b恰好走到倒数第n个节点。以下的index为倒数目标结点的索引值,两者之间的关系是index=n-1。

public int findRevNode(int index) {
        Node before = head;
        Node behind = head;
        if (index < 0 || index > length()) {
            throw new IllegalArgumentException("违法操作,索引不存在");
        } else {
            if (head == null) {
                return 0;
            }else {
                for(int i = 0;i < index;i++) {
                    before = before.next;
                }
                while(before.next != null) {
                    before = before.next;
                    behind = behind.next;
                }
            }
        }
        return behind.val;
    }

 

反转链表的思路,定义三个结点,分别为前中后,后结点指向中结点,最后前结点遍历到最后一个结点时,赋予为头结点

//反转链表
    public void reverseLink() {
        Node curNode = head;//头结点
        Node preNode = null;//前一个结点
        while(curNode != null) {
            Node nextNode = curNode.next;//保留下一个节点
            curNode.next = preNode;//指针反转
            preNode = curNode;//前结点后移
            curNode = nextNode;//当前结点后移
        }
        head = preNode;
    }

 

链表有环,类比一快一慢的人在环形跑道跑步,快的人总会和慢的人相遇。以及入环点问题。

//链表有环
    public boolean hasCycle(Node head) {
        if (head.next == null) {
            return false;
        }
        Node fast = head;
        Node slow = head;
        
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }
    
    //链表入环点
    public Node findPort(Node head) {
        //先判断是否有环
        Node fast = head;
        Node slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        
        //从链表头到环入口点等于(n - 1)循环内环 + 相遇点到环入口点,
        //在链表头和环入口点分别设置一个指针,
        //同时出发,每次各走一步,它们必定会相遇,且第一次相遇的点就是环入口点。
        slow = head;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
            
        }
        return slow;
    }

 

两个链表的相交和相交点,可以类比成y横放的形状,必有相交点,且后面的结点相同

//两个链表是否相交
    public boolean point(Node head1,Node head2) {
        if (head1 == null || head2== null) {
            return false;
        }
        while(head1.next != null) {
            head1 = head1.next;
        }
        while (head2.next != null) {
            head2 = head2.next;
        }
        if(head1 == head2) {
            return true;
        }
        else {
            return false;
        }
    }
    
    //相交链表的相交点
    public Node findPoint(Node head1,Node head2) {
        if(head1 == null || head2 == null) {
            return null;
        }
        Node p1 = head1;
        Node p2 = head2;
        int len1 = 0;
        int len2 = 0;
        int diff = 0;
        
        while(p1.next != null) {
            p1 = p1.next;    
            len1++;
        }
        while(p2.next != null) {
            p2 = p2.next;
            len2++;
        }
        if (p1 != p2) {
            return null;
        }
        diff = Math.abs(len1-len2);
        if(len1 > len2) {
            p1 = head1;
            p2 = head2;
        }else {
            p1 = head2;
            p2 = head1;
        }
        for (int i = 0; i < diff; i++) {
            p1 = p1.next;
        }
        while(p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

 

以上为单链表的练习与总结。

 

 

用java实现单链表的问题汇总

原文:https://www.cnblogs.com/mosachan/p/11909394.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!