Java单链表经典OJ题解

这篇文章介绍了Java单链表经典OJ题解，分享给大家做个参考，收藏Java资料网收获更多编程知识

        链表相关题目对掌握数据结构具有很大帮助，以下给出java单链表的经典OJ题及题解。

1.反转链表

（1）leetcode题目描述：

（2）题解样例：

class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

class Solution {
    public ListNode reverseList(ListNode head) {
        //处理空链表情况
        if(head==null){
            return null;
        }
        //处理单一节点链表情况
        if(head.next==null){
            return head;
        }
        //通过三指针方法实现反转
        ListNode pre=head;
        ListNode cur=pre.next;
        ListNode suc=cur.next;
        pre.next=null;
        while(suc!=null) {
            cur.next = pre;
            pre=cur;
            cur=suc;
            suc=suc.next;
        }
        //实现最后一个节点的反转
        cur.next=pre;
        pre=cur;
        return pre;
    }
}

（3）结果演示：

2.寻找中间节点

（1）leetcode题目描述：

（2）题解样例：

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}




public class MiddleNode {
    public ListNode middleNode(ListNode head){
        //处理空链表清空
        if(head==null){
            return head;
        }
        //通过快慢指针的方法解决
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
}

快慢指针方法即同时设定两个指针slow与fast，其中slow每次走一步，fast每次走两步，当两指针同时从头节点开始遍历时，fast走到尾节点或者为空时（尾节点说明链表节点个数为奇数，空说明节点个数为偶数），slow所在位置即为中间节点位置。

（3）结果演示：

3.返回倒数第k个节点的指针或引用

（1）leetcode题目描述：

（2）题解样例：

class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
}

public class KthtoLast {
    public  int kthtoLast(ListNode head,int k){
        //判断k的合法性
        if(k<=0) {
            return -1;
        }
        ListNode fast=head;
        ListNode slow=head;
        int count=0;
        //让fast指针先走k-1步
        while(count!=k-1){
            if(fast==null){
                return -1;
            }
            fast=fast.next;
            count++;
        }
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow.val;
    }
}

本题仍然采用快慢指针的方法，若想找到倒数第k个节点，可以让fast从头节点处先提前走k-1步，然后slow从头节点出发与发射台同步遍历链表，当fast为空时，slow的位置恰好为倒数第k个节点。

（3）结果演示：

4.合并两个升序链表

 （1）leetcode题目描述：

（2）题解样例：

 class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class MergeTwoLists {
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        //设定傀儡节点
        ListNode Nhead=new ListNode();
        //设定pre引用记录前驱节点
        ListNode pre=Nhead;
        while(headA!=null&&headB!=null){
            if(headA.val<headB.val){
                pre.next=headA;
                pre=headA;
                headA=headA.next;
            }else{
                pre.next=headB;
                pre=headB;
                headB=headB.next;
            }

        }
        //其中一个链表已经遍历完毕，只需将另一个链表剩余部分与该部分首尾相连即可
        if(headA==null){
            pre.next=headB;
        }else{
            pre.next=headA;
        }
        return Nhead.next;
    }

（3）结果演示：

5.给定x值分割链表

 （1）leetcode题目描述：

（2）题解样例：

class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
 }

public class Partition {
    public ListNode partition(ListNode head,int x){
        if(head==null){
            return null;
        }
        //设定before链表存储比x值小的节点，包括bs头节点引用和be尾节点引用
        ListNode bs=null;
        ListNode be=null;
        //设定after链表存储不比x值小的节点，包括as头节点引用和ae尾节点引用
        ListNode as=null;
        ListNode ae=null;
        ListNode cur=head;
        while(cur!=null) {
            if (cur.val < x) {
                //判断是否为第一次插入
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            }else{
                //判断是否为第一次插入
                if(as==null){
                    as=cur;
                    ae=cur;
                }else{
                    ae.next=cur;
                    ae=ae.next;
                }
            }
            cur=cur.next;
        }
        //处理全部都不小于x值的情况
        if(bs==null){
            return as;
        }
        //ae.next设定为空，避免成环
        if(as!=null){
            ae.next=null;
        }
        //合并两链表
        be.next=as;
        return bs;
    }
}

（3）结果演示：

6.判断回文链表

 （1）leetcode题目描述：

（2）题解样例：

我们当然可以通过将链表遍历取出其中的值放入数组中再判断回文的方式暴力解决，但是这种方法的空间复杂度为O（n），不符合进阶的题目要求。我们可以考虑先找到链表中间节点，再反转部分链表，之后从两边开始遍历比对的方式实现，具体代码如下：

class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
 }

 class Solution {
    public boolean isPalindrome(ListNode head) {
        //处理空链表情况
        if(head==null){
            return true;
        }
        //寻找中间节点
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //通过三指针的方法反转部分链表
        ListNode pre=slow;
        ListNode cur=pre.next;
        while(cur!=null){
            ListNode suc=cur.next;
            cur.next=pre;
            pre=cur;
            cur=suc;
        }
        //遍历比对
        while(head!=pre){
            if(head.val!=pre.val){
                return false;
            }
            //处理head与pre不可能相遇的情况
            if(head.next==pre){
                return true;
            }
            head=head.next;
            pre=pre.next;
        }
        return true;
    }
}

（3）结果演示：

7.求两个链表相交的起始节点

 （1）leetcode题目描述：

（2）题解样例：

可以采用先遍历两个链表求长度再配合快慢指针的方法解决问题。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
         val = x;
       next = null;
    }
}



public class GetIntersectionNode {
    public ListNode getIntetsectionNode(ListNode headA,ListNode headB) {
        ListNode p1=headA;
        ListNode p2=headB;
        int l1=0;
        int l2=0;
        //求链表A的长度
        while(p1!=null){
            l1++;
            p1=p1.next;
        }
        //求链表B的长度
        while(p2!=null){
            l2++;
            p2=p2.next;
        }
        p1=headA;
        p2=headB;
        int lenth=l1-l2;
        if(lenth>0){
            while(lenth!=0) {
                p1 = p1.next;
                lenth--;
            }
        }else{
                while(lenth!=0){
                    p2=p2.next;
                    lenth++;
                }
            }
        //分别遍历两个链表直到二者相遇，相遇节点恰为相交的起始节点
        while(p1!=p2){
            p1=p1.next;
            p2=p2.next;
        }
        return p1;
    }
}

（3）结果演示：

8.判断链表是否有环

 （1）leetcode题目描述：

（2）题解样例：

采用快慢指针的方法，即slow每次走一步，fast每次走两步，如此fast相对slow的速度为每次一步，所以若链表有环则遍历时fast最终必能和slow相遇，若链表无环则fast先到达链表尾部为空，循环结束。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}


public class HasCycle {
    public boolean hasCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}

（3）结果演示：

除此之外，本题也可以进阶为求环的入口节点的引用，供读者自行思考研究。

以上便是Java链表经典OJ题的全部内容，如有不当敬请斧正！

文章来源:https://blog.csdn.net/2301_79698279/article/details/140540362
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！