美文网首页
一些链表的经典题型

一些链表的经典题型

作者: 十六线程序员 | 来源:发表于2020-01-24 22:13 被阅读0次

    很久没有接触到链表,最近拉出来复习和总结下,并总结了一些常见的链表的题型。本文主要使用Java进行测试。

    链表主要有四种:单链表、双向链表、循环链表和静态链表,其中静态链表类似于数组的实现方式,需要预先分配空间大小,这里主要介绍的是动态链表即单链表、双向链表和循环链表。

    定义

    单链表
    public class SingleLinkList {
        public int data; //数据域
        public SingleLinkList next = null; //指向下一个节点
    
        public SingleLinkList(int data) {
            this.data = data;
        }
    
        public static void print(SingleLinkList singleLinkList) { // 从根节点打印数据
            System.out.println(singleLinkList.data);
            singleLinkList = singleLinkList.next;
            if (singleLinkList != null) { //节点为空就不打印了记得跳出,否则NullPointException
                print(singleLinkList);
            }
        }
    }
    
    双向链表
    public class DoubleLinkList {
        public int data; //数据域
        public DoubleLinkList front = null; //指向上一个节点
        public DoubleLinkList next = null; //指向下一个节点
    
        public DoubleLinkList(int data) {
            this.data = data;
        }
    
        public static void print(DoubleLinkList doubleLinkList) { //从根节点打印数据
            System.out.println(doubleLinkList.data);
            doubleLinkList = doubleLinkList.next;
            if (doubleLinkList != null) {
                print(doubleLinkList);
            }
        }
    }
    
    循环链表
    public class CircularLinkList {
        public int data; //数据域
        public CircularLinkList next = null; //指向下一个节点
        public static int count = 1; //跳出遍历链表的计数器
    
        public CircularLinkList(int data) {
            this.data = data;
        }
    
        public static void print(CircularLinkList circularLinkList, int limit) {
            System.out.println(circularLinkList.data);
            circularLinkList = circularLinkList.next;
            if (count < limit) { //打印limit个数据
                count ++;
                print(circularLinkList, limit);
            }
        }
    }
    
    

    为了方便测试我们写个打印数据的方法,定义好这三种链表之后,我们先初始化并给定一些数据。

    public class Solution {
        public static void main(String[] args) {
            Solution solution = new Solution();
            int arr[] = {11, 22, 33, 44, 55, 66, 77, 88, 99};
            SingleLinkList singleLinkListHead = new SingleLinkList(arr[0]); //头结点
            solution.initSingleLinkList(singleLinkListHead, arr);
            SingleLinkList.print(singleLinkListHead);
    
            DoubleLinkList doubleLinkList = new DoubleLinkList(arr[0]); //头结点
            solution.initDoubleLinkList(doubleLinkList, arr);
            DoubleLinkList.print(doubleLinkList);
    
            CircularLinkList circularLinkList = new CircularLinkList(arr[0]);//头结点
            solution.initCircularLinkList(circularLinkList, arr);
            CircularLinkList.print(circularLinkList, 20);
    
        }
    
        //初始化单链表
        public void initSingleLinkList(SingleLinkList singleLinkList, int[] arr) {
            for (int i = 1; i<arr.length; i++) {
                if (singleLinkList.next == null) {
                    singleLinkList.next = new SingleLinkList(arr[i]);
                }
                singleLinkList = singleLinkList.next;
            }
        }
    
        //初始化双向链表
        public void initDoubleLinkList(DoubleLinkList doubleLinkList, int[] arr) {
            for (int i = 1; i<arr.length; i++) {
                if (doubleLinkList.next == null) {
                    doubleLinkList.next = new DoubleLinkList(arr[i]);
                }
                DoubleLinkList frontNodes = doubleLinkList;
                doubleLinkList = doubleLinkList.next;
                doubleLinkList.front = frontNodes;
            }
        }
    
        //初始化环形链表
        public void initCircularLinkList(CircularLinkList circularLinkList, int[] arr) {
            CircularLinkList head = circularLinkList;// 记录下头结点
            for (int i = 1; i<arr.length; i++) {
                if (circularLinkList.next == null) {
                    circularLinkList.next = new CircularLinkList(arr[i]);
                }
                circularLinkList = circularLinkList.next;
            }
            circularLinkList.next = head; //尾节点指向头结点形成环
        }
    }
    

    这就定义好了测试数据了~,其中环形链表我给定了limit参数,用于指定输出的数据个数。

    常见题型

    1. 求单链表中结点的个数
    2. 将单链表反转
    3. 查找单链表中的倒数第K个结点(k > 0)
    4. 查找单链表的中间结点
    5. 从尾到头打印单链表
    6. 已知两个单链表head1和head2各自有序,把它们合并成一个链表依然有序
    7. 判断一个单链表中是否有环
    8. 判断两个单链表是否相交
    9. 求两个单链表相交的第一个节点
    10. 已知一个单链表中存在环,求进入环中的第一个节点
      待续...
    1. 求单链表中结点的个数

    emmm...这题比较简单,遍历单链表然后计数就行了。

    public int count(SingleLinkList head) {
            if (head == null) {
                return 0;
            }
            int length = 1;
            while (head.next != null) {
                head = head.next;
                length++;
            }
            return length;
        }
    
    2. 将单链表反转

    个人理解:就是让当前节点的next指向前一个节点,那么就需要建立一个临时节点用于存放前一个节点。举个栗子:
    定义链表数据为[11, 22, 33, 44],cur表示当前节点
    开始遍历该单链表...
    cur.data=11时,此时该节点为原始链表的头节点即新链表的尾节点,所以cur.next=null;
    cur.data=22时,我们目的是要让cur.next指向cur.data=11时的节点,所以需要建立临时节点用于保存cur.data=11时的节点

    public SingleLinkList reverse(SingleLinkList head) {
            if (head == null || head.next == null) {//没有头结点或者只有头结点的链表直接返回
                return head;
            }
            SingleLinkList newSingLinkList = null;
            while (head.next != null) {
                SingleLinkList temp = head.next;//临时节点 用于存放下一个节点,遍历原始链表
                head.next = newSingLinkList;//当前节点的下一个节点指向当前节点的前一个节点
                newSingLinkList = head;//存放当前节点
                head = temp;
            }
            head.next = newSingLinkList;
            newSingLinkList = head;
            return newSingLinkList;
        }
    

    方法有很多,我这里用了感觉比较好理解的方法...

    3. 查找单链表中的倒数第K个结点(k > 0)

    方法一:先求出单链表的长度n,然后再遍历到n-k就可以了。
    方法二:在查找过程中,设置两个指针,让其中一个指针比另一个指针先前移k-1步,然后两个指针同时向后移动。循环直到下一个节点为NULL,另一个指针所指向的位置就是所要找到的位置。直接看代码

    public SingleLinkList getSingleLinkListByK(int k, SingleLinkList head) {
            SingleLinkList orginal = head;
            int i = 0;
            while (i<k-1) {
                if (head== null) {
                    return null;  //超出单链表的范围了,返回
                }
                head= head.next;
                i++;
            }
            SingleLinkList tempSingleLinkList = head;//向后移动k-1步
            while (tempSingleLinkList.next!=null) {
                tempSingleLinkList = tempSingleLinkList.next;//同时移动
                orginal = orginal.next;
            }
            return orginal;
        }
    
    4. 查找单链表的中间结点

    设置两个新的链表指向头结点,第一个链表每次向后移动一位,第二个链表每次向后移动两位,当第二个链表的下一个节点指向为null时,第一个链表指的即是中间节点。

    public SingleLinkList getMiddle(SingleLinkList head) {
            if (head == null || head.next == null) {//如果只有头结点或者链表为空直接返回
                return head;
            }
            SingleLinkList first = head;
            SingleLinkList second = head;
            while (second.next != null) {
                first = first.next;
                second = second.next;
                if (second.next != null) {
                    second = second.next;
                }
            }
            return first;
        }
    
    5. 从尾到头打印单链表

    最直接的方式就是递归

    public void print(SingleLinkList head) {
            if (head == null) { //一定要有跳出递归的判断
                return;
            } else {
                print(head.next);
                System.out.println(head.data);
            }
        }
    
    6. 已知两个单链表head1和head2各自有序,把它们合并成一个链表依然有序(从小到大)

    归并排序算法,先确定头节点再开始比较两个链表的元素。

    public SingleLinkList sort(SingleLinkList head1, SingleLinkList head2) {
            SingleLinkList result;
            if (head1 == null) {
                return head2;
            }
            if (head2 == null) {
                return head1;
            }
            if (head1.data < head2.data) {//初始化头节点
                result = head1;
                head1 = head1.next;
            } else {
                result = head2;
                head2 = head2.next;
            }
            result.next = null;
            SingleLinkList temp = result;
            while (head1!= null && head2!= null) {
                if (head1.data<head2.data) {
                    temp.next = head1;
                    head1 = head1.next;
                    temp = temp.next;
                } else {
                    temp.next = head2;
                    head2 = head2.next;
                    temp = temp.next;
                }
                temp.next = null;
            }
            if (head1!= null) {
                temp.next = head1;
            } else {
                temp.next = head2;
            }
            return result;
        }
    
    7. 判断一个单链表中是否有环

    使用快慢指针方法,定义两个单链表指向头节点,快指针每次移动2个位置,慢指针每次移动1个位置,如果两个指针能够相遇,则说明该单链表有环。

    public boolean annular(SingleLinkList head) {
            SingleLinkList head1 = head;
            SingleLinkList head2 = head;
            while (head1.next != null && head2.next != null) {
                head1 = head1.next;//慢指针
                head2 = head2.next.next;//快指针
                if (head1 == head2) {
                    return true;
                }
            }
            return false;
        }
    
    8. 判断两个单链表是否相交

    方法1:可以对每个节点进行hash,再遍历两个单链表,当存在hash值相同的节点时,说明两个单链表相交。
    方法2:两个单链表相交,说明两个单链表的最后一个节点肯定相同,直接看代码。

     public boolean intersect(SingleLinkList head1, SingleLinkList head2) {
            if (head1 == null || head2 == null) {
                return false;
            }
            SingleLinkList temp1 = head1;
            SingleLinkList temp2 = head2;
            while (temp1.next != null) {
                temp1 = temp1.next;
            }
            while (temp2.next != null) {
                temp2 = temp2.next;
            }
            return temp1 == temp2;
        }
    
    9. 求两个单链表相交的第一个节点

    方法1:求出两个单链表的长度分别为len1,len2,先让长的单链表移动|len1-len2|步,再同时遍历两个单链表,遇到的第一个相同节点即交点。
    方法2:已知两个单链表相交,可以让尾节点指向其中一个链表的头节点,这样就转化为一个有环单链表,题目就转化为求有环链表的入环点,和第10题一样。

    10. 已知一个单链表中存在环,求进入环中的第一个节点

    未完成。。待续。。

    相关文章

      网友评论

          本文标题:一些链表的经典题型

          本文链接:https://www.haomeiwen.com/subject/sxzkzctx.html