[数据结构与算法] leetcode-hot100-链表部分

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> leetcode-hot100-链表部分 -> 正文阅读

[数据结构与算法]leetcode-hot100-链表部分

文章目录

2. 两数相加 - 力扣（LeetCode） (leetcode-cn.com)

思路：
1. 对两个链表进行判断，为空返回另外一个。
2. 因为涉及到相加，所以要设置一个进位数，每次相加的时候要加上进位数。
3. 如果和大于9，那么进位数=和/10，和-=10，否则，进位数重置为0，
4. 采用尾插法。结束之后要对另外两个链表判空。
5. 本题最好建立一个虚拟头结点。

代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        int sum = 0, carry = 0;
        while(l1 != null && l2 != null){
            sum = l1.val + l2.val + carry;
            if(sum > 9){
                carry = sum / 10;
                sum -= 10;
            }else {
                carry = 0;
            }
            ListNode s = new ListNode(sum);
            p.next = s;
            p = p.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        while(l1 != null){
            sum = l1.val + carry;
            if(sum >= 10){
                carry = sum / 10;
                sum -= 10;
            }else {
                carry = 0;
            }
            ListNode s = new ListNode(sum);
            p.next = s;
            p = p.next;
            l1 = l1.next;
        }
        while(l2 != null){
            sum = l2.val + carry;
            if(sum >= 10){
                carry = sum / 10;
                sum -= 10;
            }else {
                carry = 0;
            }
            ListNode s = new ListNode(sum);
            p.next = s;
            p = p.next;
            l2 = l2.next;
        }
        if(carry != 0){
            ListNode s = new ListNode(carry);
            p.next = s;
            p = p.next;
        }
        return dummy.next;
    }

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (leetcode-cn.com)

思路：
1. 先翻转链表。
2. 然后从翻转的反删除第n个节点，（eg：删除倒数第二个，也就是删除正数第二个节点）。
3. 同样要使用虚拟节点。

代码

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // return reverse(head);
        ListNode newHead = reverse(head);
        ListNode dummy = new ListNode();
        dummy.next = newHead;
        ListNode p = dummy, pre = null;
        while(n != 0){
            pre = p;
            p = p.next;
            n--;
        }
        pre.next = p.next;
        return reverse(dummy.next);


    }
    public ListNode reverse(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = head, q = head.next, h;
        while(q != null){
            h = q.next;
            q.next = p;
            p = q;
            q = h;
        }
        head.next = null;
        return p;
    }
}

21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)

思路：
1. 合并链表的关键就是值的比较。
2. 采用虚拟节点进行尾插法。

代码

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                p.next = l1;
                l1 = l1.next;
            }else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        while(l1 != null){
            p.next = l1;
            p = p.next;
            l1 = l1.next;
        }
        while(l2 != null){
            p.next = l2;
            p = p.next;
            l2 = l2.next;
        }
        return dummy.next;
    }
}

23. 合并K个升序链表 - 力扣（LeetCode） (leetcode-cn.com)

思路：
1. 采用两两合并的方法，最开始是空和第一个元素进行合并。

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = null;
        for(int i = 0; i < lists.length; i++){
            res = mergerTwo(res, lists[i]);
        }
        return res;
    }
    public ListNode mergerTwo(ListNode l1, ListNode l2){
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                p.next = l1;
                l1 = l1.next;
            }else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        while(l1 != null){
            p.next = l1;
            p = p.next;
            l1 = l1.next;
        }
        while(l2 != null){
            p.next = l2;
            p = p.next;
            l2 = l2.next;
        }
        return dummy.next;
    }
}

方法2：使用二分将问题的规模进一步的缩小，因为题目说了每个链表都已经按照升序进行了排列。

代码：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if(n == 0){
            return null;
        }
        return recursion(lists, 0, n - 1);
    }

    public ListNode recursion(ListNode[] lists, int left, int right){
        //注意要有递归的跳出边界
        if(left == right){
            return lists[left];
        }
        int mid = left + ((right - left) >> 1);
        ListNode leftList = recursion(lists, left, mid);
        ListNode rightList = recursion(lists, mid + 1, right);
        return mergeTwoLists(leftList, rightList);
    }

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

141. 环形链表 - 力扣（LeetCode） (leetcode-cn.com)

思路：

快慢指针都固定到头结点。
因为快指针要移动两个位置，所以要对快指针做两次判断，进入循环后，快慢指针各自移动，只要二者相等，那么就返回true，如果循环结束还没有相等，返回false

代码

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

142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)

思路：与上一题一样，只是在最后的时候新增判断，不让指针为空，为空了就返回null；

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            if(head == head.next){
                return head;
            }else {
                return null;
            }
        }
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }
        fast = head;
        while(slow != fast && slow != null && fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        if(slow == null || fast == null){
            return null;
        }
        return fast;
    }
}

注意点：

如果只有一个节点或者空链表，那么返回的是null，不是head。
在找环的时候，快慢都在head，与142不一样，本题是在死循环里面进行，首先判断的是快指针是否为空以及快指针下一个位置是否为空，这样才能进行向下进行两个指针移动。

146. LRU 缓存机制 - 力扣（LeetCode） (leetcode-cn.com)

简单阐述LRU(Least Recently Used)，在内存中，当内存满的时候，有新的记录要添加，删除的就是最长时间没有被访问的。如果某个记录被访问了，那么，将这个记录重新置顶。其余的记录依次后移。
思路：使用map+双链表。

写一个双链表的类。

class LinkedNode{
    int key;
    int value;
    LinkedNode pre;
    LinkedNode next;
    public LinkedNode(){

    }
    public LinkedNode(int key, int value){
        this.key = key;
        this.value = value;
    }
}

在LRUCache类中，要初始化一个map，这个map就是用来记录每次put进去的值，并初始化一个大小size，用来记录每次操作完成之后cache的大小，同时初始化头尾节点，并使头尾相连。
get(int key)的方法作用就是获取在缓存中的记录。如果缓存中存在这个记录，那么就让这个记录到第一位，并返回它的值。
put(int key, int value)方法作用就是向缓存中放入数据。每次先从缓存中确认是否有记录。
1. 如果有记录，那么只需要将这次给的value值重新设置即可，并将此条记录移动到头部。
2. 如果没有记录，那么就重新创建一个节点，用来描述这个记录，然后放入缓存中，并将此记录添加到首位置，同时添加后的cache大小要记录。如果此时添加之后的大小比初始给定cache的大小大的话，那么需要移除最靠近靠近尾部的记录，因为此记录已经太久没有被访问了。然后再记录此时的cache大小。

注：

四个函数的意思：因为LRU机制，所以需要两个函数，一个是移动至头的moveToHead(LinkedNode node)函数、一个是删除尾结点removeTail()函数。第一个函数需要做的是将传入的节点，先删除该节点（假设该节点存在双链表中），然后再移动添加至头结点中。第二个函数首先需要获取尾指针前面的节点，然后删除该节点，并返回该节点。分析就需要四个函数：1、添加至头2、删除结点3、移动至头4、删除尾结点

代码

class LinkedNode{
   int key;
   int value;
   LinkedNode pre;
   LinkedNode next;
   public LinkedNode(){

   }
   public LinkedNode(int key, int value){
       this.key = key;
       this.value = value;
   }
}

class LRUCache {

   private Map<Integer, LinkedNode> cache = new HashMap<>();
   private int size;
   private int capacity;
   private LinkedNode head, tail;

   public LRUCache(int capacity) {
       this.size = 0;
       this.capacity = capacity;
       head = new LinkedNode();
       tail = new LinkedNode();
       head.next = tail;
       tail.pre = head;
   }
   
   public int get(int key) {
       LinkedNode node = cache.get(key);
       if(node == null){
           return -1;
       }
       moveToHead(node);
       return node.value;
   }
   
   public void put(int key, int value) {
       LinkedNode node = cache.get(key);
       if(node == null){
           LinkedNode newNode = new LinkedNode(key,value);
           //新节点首先要放入cache中，然后再加入到链表的头
           cache.put(key,newNode);
           addTohead(newNode);
           ++size;
           if(size > capacity){
               LinkedNode tail = removeTail();
               //从缓存中获取待删除的key，因为是用map记录的，所以使用map自带的方法remove()删除
               cache.remove(tail.key);
               --size;
           }
       }else {
           node.value = value;
           moveToHead(node);
       }
   }

   private void addTohead(LinkedNode node){
       node.pre = head;
       node.next = head.next;
       head.next.pre = node;
       head.next = node;
   }

   private void removeNode(LinkedNode node){
       node.pre.next = node.next;
       node.next.pre = node.pre;
   }

   private void moveToHead(LinkedNode node){
       removeNode(node);
       addTohead(node);
   }

   private LinkedNode removeTail(){
       LinkedNode res = tail.pre;
       removeNode(res);
       return res;
   }
}

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/

记录一下：

额外四个方法：
添加到头（新节点使用）
删除结点（老结点移动的时候使用）
移动到头（老结点被重新访问，先添加到头，再删除本结点）
删除尾部（新添加的节点导致容量爆出，删除尾部，就是最久未访问的节点）
除了最后一个方法，其他的都要传入结点node。

 初始化cache的时候，要有size，要有capacity，要有head，要有tail，head、tail连起来

148. 排序链表 - 力扣（LeetCode） (leetcode-cn.com)

思路：还是使用快慢指针的方法。

使用两个辅助函数。
一个函数用来合并两个链表(merge)，一个函数用来不断的拆分链表之后进行合并再排序(sort)。
sort函数（参数是头尾）中使用快慢指针，找到中点，将慢指针指向的链表赋给mid，（注：快慢指针的移动，只有当快指针不等于尾的时候才进入，两次判断，每次值下移当前的下一步）。
1. 然后将链表从(head-mid)进行一次排序，(mid-tail)进行一次排序，目的就是将整个链表不断拆分，即：递归，递归完成之后再还原，这样就能将整个链表进行合并了。
merge函数（参数是两个链表）用来合并给定的两个链表。

本题的快慢指针是，快指针两次判断的条件都是不等于尾。
代码：

class Solution {
    public ListNode sortList(ListNode head) {
        return sort(head, null);
    }

    public ListNode sort(ListNode head, ListNode tail){
        if(head == null){
            return head;
        }
        if(head.next == tail){
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while(fast != tail){
            slow = slow.next;
            fast = fast.next;
            if(fast != tail){
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sort(head,mid);
        ListNode list2 = sort(mid, tail);
        ListNode res = megerList(list1,list2);
        return res;
    }

    public ListNode megerList(ListNode l1, ListNode l2){
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                p.next = l1;
                l1 = l1.next;
            }else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if(l1 != null){
            p.next = l1;
        }
        if(l2 != null){
            p.next = l2;
        }
        return dummy.next;
    }
}

160. 相交链表 - 力扣（LeetCode） (leetcode-cn.com)

思路：

计算两个链表的长度，计算他们的差值，

链表长度大的设为Longer，另一个就是shorter，长的每次下移，只要还有差值，移动一次差值–
如果longer==shorter，那么返回其中任意一个即可，否则，两个指针都下移一步。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        int len1 = 0, len2 = 0;
        ListNode p = headA, q = headB;
        while(p != null){
            len1++;
            p = p.next;
        }
        while(q != null){
            len2++;
            q = q.next;
        }
        int dif = len1 > len2 ? len1 - len2 : len2 - len1;
        ListNode longer = null, shorter = null;
        if(len1 > len2){
            longer = headA;
            shorter = headB;
        }else {
            longer = headB;
            shorter = headA;
        }
        while(dif > 0){
            longer = longer.next;
            dif--;
        }
        while(longer != null && shorter != null){
            if(longer == shorter){
                return longer;
            }else {
                longer = longer.next;
                shorter =shorter.next;
            }
        }
        return null;

    }
}

206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)

思路：

设置三个工作指针，分别用来记录前一个节点，当前结点以及下一个节点信息。

前一个节点就是head，当前结点head.next，下一个节点先置空。
只要当前结点不为空，每次先保存下一个节点信息，当前结点指向前一个节点，前一个节点改变为当前结点，下一个节点为当前结点。
最后将原head.next置空即可。返回前一个节点（当前结点此时保存翻转后的链表信息）

代码：

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = head, q = head.next, h = null;
        while(q != null){
            h = q.next;
            q.next = p;
            p = q;
            q = h;
        }
        head.next = null;
        return p;
    }
}

234. 回文链表 - 力扣（LeetCode） (leetcode-cn.com)

思路：

使用翻转+快慢指针的思想。
先找到中点，翻转慢指针之后的链表，此时慢指针指向中点，并对慢指针开始的下一个位置（即：下一个指针指向的链表）进行翻转。
从慢指针的下一个位置断开，此时值需要判断是否两个节点值相等，不相等就下移。

代码

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        ListNode fast = head.next, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode reverseHead = reverse(slow.next);
        slow.next = null;
        while(head != null && reverseHead != null){
            if(head.val != reverseHead.val){
                return false;
            }else {
                head = head.next;
                reverseHead = reverseHead.next;
            }
        }
        return true;
        
    }
    public ListNode reverse(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = head, q = head.next, h = null;
        while(q != null){
            h = q.next;
            q.next = p;
            p = q;
            q = h;
        }
        head.next = null;
        return p;
    }
}

25. K 个一组翻转链表 - 力扣（LeetCode） (leetcode-cn.com)

思路：

使用虚拟头结点，连接到给定链表。
设置两个工作指针pre和p。p指针的作用是找到待断开的节点位置，pre指向上一次翻转完成之后的节点位置。
进入外循环，只要p的下一个位置不为空，
1. 在循环，内部循环的条件是要移动的次数以及p不为空，那么在内循环p就每次下移。
2. 如果p下移到空节点，那么说明已经所有的完成了，直接break掉。
3. 使用两个工作节点，start和next，前者保存每次要翻转的小段链表，后者保存每次从p之后断开的节点信息。
4. 从p之后断开。
5. pre的下一个位置就开始翻转区间链表。
6. 翻转完成后，start在后面，将start的下一个位置连接之间保存的next节点。
7. p和pre同时又回到翻转之后的start位置。
返回dummy.next。

代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre = dummy, p = dummy;
        while(p.next != null){
            //这个for循环就是找到待翻转断开的位置。
            for(int i = 0; i < k && p != null; i++){
                p = p.next;
            }
            //如果为空，那么就说明已经工作完成
            if(p == null){
                break;
            }
            //start永远指向待翻转的头
            ListNode start = pre.next;
            //next永远指向翻转结束的下一个节点，保存结点信息。
            ListNode next = p.next;
            //从p位置断开。
            p.next = null;
            //进行连接
            pre.next = reverse(start);
            start.next = next;
            //翻转完毕之后，start到了尾部，那么pre还是指向下一次开始的头部，即start
            pre = start;
            //p和pre永远在一起
            p = pre;
        }
        return dummy.next;
    }
    public ListNode reverse(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = head, q = head.next, h = null;
        while(q != null){
            h = q.next;
            q.next = p;
            p = q;
            q = h;
        }
        head.next = null;
        head = p;
        return head;
    }
}

138. 复制带随机指针的链表 - 力扣（LeetCode） (leetcode-cn.com)

思路：

先进行判空处理，这里值需要判断当前是否为空，不需要判断下一个为空。
从next方向进行copy，等到在next方向上的链表。
然后再从random方向进行复制，此时的情况是1->1’->2->2’，所以这个时候，要读copy的链表进行赋值的时候，只需要看原链表当前结点有没有random域。有就赋给random.next，没有就是空。
然后再做分割
- 分割也是从next方向进行分割

代码：

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
        Node p = head;
        Node nextNode = null;
        while(p != null){
            nextNode = p.next;
            Node s = new Node(p.val);
            s.next = p.next;
            p.next = s;
            p = nextNode;
        }
        p = head;
        Node copy = null;
        while(p != null){
            nextNode = p.next.next;
            copy = p.next;
            if(p.random != null){
                copy.random = p.random.next;
            }else {
                copy.random = null;
            }
            p = nextNode;
        }
        //分割
        Node res = head.next;
        p = head;
        while(p != null){
            nextNode = p.next.next;
            copy = p.next;
            p.next = nextNode;
            if(nextNode != null){
                copy.next = nextNode.next;
            }else {
                copy.next = null;
            }
            p = nextNode;
        }
        return res;
    }
}

 第一步：复制水平方向的节点，保存下一个节点的信息。
 第二步：水平方向复制了之后，原链表的下一个节点就是两次next，先报该节点信息进行保存。然后进行random方向的连接。
 第三步：水平方向的分割。在分割时候同样要记录下一个节点以及下下个节点的位置信息。

代码的细节：
- 在next方向进行copy的时候，要先保存下一个节点，不能在最后直接进行.next.next，因为这样可能.next为空。每次完成copy的时候，就把保存的节点给当前工作节点。
- 在random方向上进行copy的时候，因为存在copy节点，所以每次保存的时候要存取.next.next，不会存在为空的情况。同样把保存结点给工作节点。
- 分割的时候，设置一个结果res，用来返回
  - 将工作指针指向头，返回结果指向第一个节点的下一个。
  - 在循环体内，先保存原链表的节点.next.next。记录复制的节点.next
  - 把原来的链表进行连接，p.next=.next.next。
  - 复制的节点如何连接？
    - 首先判断.next.next存不存在，存在就连，不存在就不连。

92. 反转链表 II - 力扣（LeetCode） (leetcode-cn.com)

思路：

使用翻转链表的思想。
设置虚拟头结点。连接链表。
设置四个工作指针，start（指向待翻转的头结点）、end（翻转部分的尾结点）、startPre（翻转节点之前的那个节点）以及endNext（翻转结束之后的尾结点）。
保存四个节点的信息。分别从startPre和end两个位置断开。
翻转start部分链表。
翻转完成进行连接。
返回dummy.next。

代码：

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode p = dummy;
        ListNode start = null, end = null, startPre = null, endNext = null;
        while(left - 1 > 0){
            p = p.next;
            left--;
        }
        startPre = p;
        start = p.next;
        p = head;
        while(right - 1 > 0){
            p = p.next;
            right--;
        }
        end = p;
        endNext = p.next;
        startPre.next = null;
        end.next = null;
        ListNode reverseNode = reverse(start);
        startPre.next = reverseNode;
        start.next = endNext;
        return dummy.next;
    }
    public ListNode reverse(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = head, q = head.next, h = null;
        while(q != null){
            h = q.next;
            q.next = p;
            p = q;
            q = h;
        }
        head.next = null;
        head = p;
        return head;
    }
}

143. 重排链表 - 力扣（LeetCode） (leetcode-cn.com)

思路：

使用到三个辅助函数，一个用来找中点，一个用来翻转，一个用来合并数组，但是本题的合并并不是从大到小，而是顺序相连。
先找到给定链表的中点，然后记录下后面链表的信息，断开，然后翻转后面链表。
最后只需要合并前面的链表和翻转之后的链表。
合并函数中，只要给定的两个链表都不为空，那么使用两个变量保存各自下一个节点信息，第一个链表的next连接第二个节点的头，连接完成之后，第一个指针下移到自己保存的下一个节点位置，第二个链表操作也一样。

总结：

找中点，断开，翻转后面滴，连接两链表。

代码：

/**
 * Definition for singly-linked list.
 * public 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 void reorderList(ListNode head) {
        if(head == null){
            return;
        }
        ListNode mid = fingMid(head);
        ListNode l2 = mid.next;
        mid.next = null;
        l2 = reverse(l2);
        ListNode l1 = head;
        mergeTwo(l1, l2);

    }

    public ListNode fingMid(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = head, q = head.next, h = null;
        while(q != null){
            h = q.next;
            q.next = p;
            p = q;
            q = h;
        }
        head.next = null;
        head = p;
        return head;
    }
    public void mergeTwo(ListNode head1, ListNode head2) {
    ListNode next1 = null;
    ListNode next2 = null;
    while (head1 != null && head2 != null) {
        next1 = head1.next;
        next2 = head2.next;

        head1.next = head2;
        head1 = next1;

        head2.next = head1;
        head2 = next2;
        }
    }
}

83. 删除排序链表中的重复元素 - 力扣（LeetCode） (leetcode-cn.com)

思路：

虚拟头节点连接连接。
工作指针设置到p.next。
所以循环条件就是p.next != null，判断就是当前工作指针的值和工作指针下一个位置值是否相等
1. 相等那个q = p.next，然后一直找到q应该停的位置。最后p.next = q；
2. 不相等p下移。
最后返回dummy.next。

代码：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode p = dummy.next;
        ListNode q = null;
        while(p.next != null){
            if(p.val == p.next.val){
               q = p.next;
               while(q != null && q.val == p.next.val){
                q = q.next;
               }
               p.next = q;
            }else {
                p = p.next;
            }
        }
        return dummy.next;
    }
}

82. 删除排序链表中的重复元素 II - 力扣（LeetCode） (leetcode-cn.com)

思路：

判空处理
使用虚拟头结点连接
设置一个q指针，用来保存不重复的节点。工作指针p设置在虚拟头结点。
只要p的下一个位置以及下下一个位置不为空，进入循环
1. 如果p下一个位置值等于下下个位置的值，那么q就指向p的下一个位置。同时q要不断的寻找它合适位置，就是它的值只要等于p下一个值为的值，q就不断下移。
2. 否则p下移。
最后返回虚拟节点下一个位置。

代码：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode p = dummy;
        ListNode q = null;
        while(p.next != null && p.next.next != null){
            if(p.next.val == p.next.next.val){
                q = p.next;
                while(q != null && q.val == p.next.val){
                    q = q.next;
                }
                p.next = q;
            }else {
                p = p.next;
            }
        }
        return dummy.next;
    }
}