LeetCode笔记--链表

160.链表有关的几个题目

给出如下链表类

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

160.找到相交链表的第一个焦点

两个指针都从头开始 一直往下遍历 当一个走到结尾了 就让它从另一个链表的头开始走 这样一来 两者的行进的距离最后都是相等的 例如上面的行进的情况就是

A:a1 a2 c1 c2 c3 b1 b2 b3 c1

B:b1 b2 b3 c1 c2 c3 a1 a2 c1

对于此题 刷题的力扣网友给出了诗意的描述

走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。

有丶东西 真就是代码界我写诗最强 诗歌界我代码最强

代码如下

public ListNode getIntersectionNode(ListNode headA, ListNode headB)
    {
        ListNode pa=headA;
        ListNode pb=headB;
        while (pa!=pb)
        {
            if (pa!=null)pa=pa.next;
            else pa=headB;
            if (pb!=null)pb=pb.next;
            else pb=headA;

        }
        return pa;
    }

206.反转链表

这个没什么好说的 在遍历的时候用一个前驱一个后记来记录下来 然后指针摆动 依次进行下去就行

if (head==null)return null;
ListNode pre=null;
ListNode cur=head;
while (true)
{
    if (cur.next==null)
    {
        cur.next=pre;
        return cur;
    }
    ListNode next = cur.next;
    cur.next=pre;
    pre=cur;
    cur=next;
}

这里做题的时候碰到了个小问题 就是每一轮操作 其实都只是cur 前面的链表的部分完成了反转 然后下一轮才通过cur.next=pre;这个操作将他们连接起来 但是我在cur.next==null的时候没有进行这一部导致最后的结果只有一个末尾的元素 记一下吧

21.合并有序链表

这个也没啥好说的 跟合并有序线性表差不多就是再new一个新的链表来装元素 两个链表同时遍历 比较大小 取小的那个 然后然后被取走的这个链表的对应的指针++ 直到其中的一个链表的指针为空结束

然后判断是否还有表不为空 就把剩余的元素也都添加进来就行了代码如下

public ListNode mergeTwoLists(ListNode l1, ListNode l2)
    {
        if (l1==null)return l2;
        if (l2==null)return l1;
        ListNode p1=l1;
        ListNode p2=l2;
        ListNode res;
        if (p1.val<p2.val)
        {
            res = new ListNode(p1.val);
            p1=p1.next;
        }
        else
        {
            res = new ListNode(p2.val);
            p2=p2.next;
        }
        ListNode resP=res;
        while (p1!=null&&p2!=null)
        {
            if (p1.val<p2.val)
            {
                resP.next = new ListNode(p1.val);
                p1=p1.next;
            }
            else
            {
                resP.next = new ListNode(p2.val);
                p2=p2.next;
            }
            resP=resP.next;
        }
        while (p1!=null)
        {
            resP.next= new ListNode(p1.val);
            resP=resP.next;
            p1=p1.next;
        }
        while (p2!=null)
        {
            resP.next = new ListNode(p2.val);
            resP=resP.next;
            p2=p2.next;
        }
        return res;
    }

83.删除链表中的重复元素

这个题就是定义两个指针 一个快一个慢 快的往前面探路 慢的在后面等着 如果快的值不等于慢的值就让慢的next=快 然后让慢的移动到next 直到快指针走完全程 当然了首先判断是否为空 老生常谈了 还是要记住的,最后走完之后不要忘记将慢指针的next置为空代码如下

public ListNode deleteDuplicates(ListNode head) {
        if (head==null)return null;
        ListNode left=head;
        ListNode right=head;
        while (right!=null)
        {
            if (left.val!=right.val)
            {
                left.next= right;
                left=left.next;
            }
            right=right.next;
        }
        left.next=null;
        return head;
    }

725.分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。
这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。
举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

把每个子序列的头结点存入数组即可 首先我们要计算的是这个链表的长度 得到长度 然后len%k就可以得到剩余多少个单独的元素 这代表着前多少个数组的元素代表的子链表可以多放一个节点 例如1 2 3 4 5 k=3 得到的序列就是
[(1->2),(3-4),5] 然后用len/k得到每一个子链表假设没有多余的情况下理论该放多少个元素 例如上面的就是1 但是5%3得到2 所以前2个数组元素多加了一个节点 得到了每个数组元素存放的元素的个数就可以开始赋值了 其中需要注意几个问题

• 每一个子链表结尾最后需要把next 赋值为Null
• 在得到通过子链表的长度然后对总链表进行指针移动的时候 每次只需要移动子链表-1次 因为我们每次都是从子链表的第一个节点开始的 具体如何赋值看代码

public ListNode[] splitListToParts(ListNode root,int k)
    {
        ListNode p=root;
        int len=0;
        while (p!=null)
        {
            len++;
            p=p.next;
        }
        ListNode res[]=new ListNode[k];
        int surplus=len%k;
        int baseNumOfEveryElement=len/k;
        ListNode cur=root;
        for (int i = 0; i < res.length; i++)
        {
            ListNode head=cur;
            res[i]=head;
            int sonListLength=baseNumOfEveryElement+(i<surplus?1:0);
            for (int j = 1; j < sonListLength; j++)
            {
                if (cur!=null)cur=cur.next;
            }
            if (cur!=null)
            {
                ListNode next=cur.next;
                cur.next=null;
                cur=next;
            }
        }
        return res;
    }

243 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

输入：head = [1,2,3,4]
输出：[2,1,4,3]
采用递归思想求解 将每一次交换看成是一个子序列 传入头节点 递归调用 递归的尽头就是当head==null||head.next==null的时候 直接return head
递归体 先把head.next存下来然后把head,next指向下一个子序列(等会提柜完成要返回子链表的头结点的) 然后刚才保存下来的暂且记录为head.next节点暂且记录为x节点 也就是没有交换之前的第二个节点 让x.next=head即可 代码如下

public ListNode swapPairs(ListNode head) {
        if (head==null||head.next==null)return head;
        ListNode next=head.next;
        head.next=swapPairs(next.next);
        next.next=head;
        return next;
    }

注意 递归调用时传入的next.next

234.判断回文链表

这种题跟判断回文数组回文串一样的解法 暴力的话可以把他存到一个数组里面然后头和尾指针往中间靠近判断是否相等即可 复杂度高
另一种方法 hash法
如何理解这个串 我个人理解的hash算法 就是让一个对象hash之后能够成为一个独立的序列 例如这个链表 其实这个整个链表可以看成是一个数 这个数字是什么呢 每一个节点的值就对应我平常十进制数类似的1234这样的数位 然后有一个seed 也就是进制 换句话说1234可以看成是1->2->3->4链表 用seed=10 做hash之后的数字 可以看到 如果这个链表他是一个回文的 那么我逆序hash和顺序hash 得到的hash值应该是一样的 例如1->2->3->3->2->1 得到的都是十进制123321这个值 选取seed的时候需要选取一个质数 这样才能保证得到的hash序列只有一个值与其对应 也就是为了避免所谓的hash冲突吧 个人理解
如此一来可以得到如下代码

public boolean isPalindrome(ListNode head) {
        ListNode p=head;
        long seed=17;
        long hash1=0;
        long hash2=0;
        long index=1;  //累计到现在的指数与种子的乘积
        while (p!=null)
        {
            hash1=hash1*seed+p.val;
            hash2=hash2+index*p.val;
            index*=seed;
            p=p.next;
        }
        return hash1==hash2;
    }

注意: 这里的hash值就算超出了long范围也没关系 也是可以判断的 但是会有极小概率出现冲突 还有就是 在逆序计算hash值的时候index注意不要溢出了导致计算结果错误 我出错的一个原因就是index是int型了 结果导致溢出 出错

seed选取的是质数17 hash1就是顺序hash 把第一位数字当做最高位 与我们平时的书写习惯相符合 hash2就是逆序hash当然就是相反的了
这两种hash的计算方法其实与我们计算整数幂没有区别 例如hash1就是每次都用当前的hashseed+当前位置的值 例如1234 就是1=010+1,12=110+2...以此类推 第二种就要借助一个index变量计算当前的seed是乘到几次方来了 还是用1234来类比就是 4=0+41 (1就是10 的零次方),34=4+10*3...以此类推

类比一下 遇到回文串 其实只需要根据当前的字母能取到的范围来定一个seed 并且 把每个字母-基准字符 得到一个数字
例如 假设之后26个小写英文字母 那我的seed就可以取29 然后去'a'作为基准 串中的'a'就是代表数字0 ...'z'代表25这样 一样可以计算hash值
最后判断两个hash值是否相等 等于的话就是回文串