Java-数据结构-链表＜一＞

一. 链表简单介绍

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）[1]，通常链表的头被称为head，尾部一般用null表示。【图自[1]】

链表的类型有单链表，双链表，循环链表等。数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。链表是通过指针域的指针链接在内存中各个节点。

二. 链表的代码实现

leetcode中对单向链表的典型实现

  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; }
  }

三. leetcode&牛客实例

1. leetcode206 && nowcoderBM1 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

（1）数组（list）方法：全部将值取出再重新赋值

class Solution {
    public ListNode reverseList(ListNode head) {
        //1.全部取值重新赋值
        return reverseList1(head);
    }
    public ListNode reverseList1(ListNode head){
        if(head == null) return null;
        LinkedList<Integer> list = new LinkedList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        ListNode new_head = new ListNode(list.removeLast());
        ListNode cur = new_head;
        ListNode temp;
        while(!list.isEmpty()){
            temp = new ListNode(list.removeLast());
            cur.next = temp;
            cur = temp;
        }
        return new_head;
    }
}

（2）原地反转

原地反转需要三个指针，三个指针在这里分别定义为tail,middle,pre。

class Solution {
    public ListNode reverseList(ListNode head) {
        //2.原地反转
        return reverseList2(head);
    }
    
    public ListNode reverseList2(ListNode head){
        if(head == null) return null;
        ListNode tail = head;
        if(tail.next == null) return tail;
        ListNode middle = head.next;
        ListNode pre = middle.next;
        tail.next = null;
        while(middle.next != null){
            middle.next = tail;
            tail = middle;
            middle = pre;
            pre = pre.next;
        }
        middle.next = tail;
        return middle;
    }
}

（3）构建新链表（头插法）

class Solution {
    public ListNode reverseList(ListNode head) {
        //3.构建新链表
        return reverseList3(head);
    }
    public ListNode reverseList3(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode new_head = new ListNode(head.val);
        new_head.next = null;
        ListNode temp = head.next;
        ListNode cur = new_head;
        while(temp.next != null){
            head = temp.next;
            temp.next = cur;
            cur = temp;
            temp = head;
        }
        temp.next = cur;
        return temp;
    }
}

（4）递归

class Solution {
    public ListNode reverseList(ListNode head) {
        //5.递归
        return reverseList5(head);
    }
    public ListNode reverseList5(ListNode head) {
    // 1. 递归终止条件
    if (head == null || head.next == null) {
        return head;
    }
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
    }
}

2. leetcode21 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

双指针

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p1 = list1;
        ListNode p2 = list2;
        ListNode new_pre = new ListNode(0);
        ListNode cur = new_pre;
        while(p1 != null && p2 != null){
            if(p1.val < p2.val){
                cur.next = p1;
                cur = cur.next;
                p1 = p1.next;
            }
            else{
                cur.next = p2;
                cur = cur.next;
                p2 = p2.next;
            }
        }
        if(p1 == null){
            cur.next = p2;
        }
        if(p2 == null){
            cur.next = p1;
        }
        return new_pre.next;
    }
}

递归

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }
        else if(list2 == null){
            return list1;
        }
        else if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }
        else{
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}

3. leetcode83 删除链表中的重复元素

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

输入：head = [1,1,2,3,3]
输出：[1,2,3]

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        ListNode tail = head;
        ListNode pre = tail.next;
        while(pre != null){
            if(tail.val == pre.val){
                pre = pre.next;
            }
            else{
                tail.next = pre;
                tail = pre;
                pre = pre.next;
            }
        }
        if(tail.next == null) return head;
        tail.next = null;
        return head;
    }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) {return null;}
        ListNode t1 = head;
        ListNode t2 = head.next;
        while(t2 != null){
            if(t1.val == t2.val){
            t1.next = t2.next;
            t2 = t1.next;
            }
            else{
                t1 = t2;
                t2 = t2.next;
            }
        }
         return head;
        }
       
    }

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

4. leetcode141 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。否则，返回 false 。

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

HashSet方法：

public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> list = new HashSet<>();
        while(head != null){
            if(list.contains(head)){
                return true;
            }
            else{
            list.add(head);
            head = head.next;
            }
        }
        return false;
    }
}

双指针：

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

5. leetcode234 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

输入：head = [1,2,2,1]
输出：true

双指针+栈

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next == null) return true;
        ListNode slow = head;
        ListNode fast = head;
        Deque<Integer> list = new ArrayDeque<>();
        while(fast != null && fast.next != null){
            list.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        } 
        if(fast == null){
            while(slow != null){
                if(slow.val != list.pop()){
                    return false;
                }
                slow = slow.next;
            }
        }
        else{
            slow = slow.next;
            while(slow != null){
                if(slow.val != list.pop()){
                    return false;
                }
                slow = slow.next;
            }
        }
        return true;
    }
}

双指针+反转

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next == null) return true;
        ListNode slow = head;
        ListNode fast = head;
        ListNode tail = null;
        while(fast != null && fast.next != null){
            //slow = slow.next;
            fast = fast.next.next;
            ListNode temp = slow;
            slow = slow.next;
            temp.next = tail;
            tail = temp;
        } 
        if(fast != null){
            slow = slow.next;
        }
        while(slow != null){
            if(slow.val != tail.val){
                return false;
            }
            slow = slow.next;
            tail = tail.next;
        }
        return true;
    }
}

6. leetcode92 反转链表II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyhead = new ListNode(0);
        dummyhead.next = head;
        ListNode tail = dummyhead;
        ListNode pre = dummyhead.next;
        for(int i = 0; i < left-1; i++){
            tail = tail.next;
            pre = pre.next;
        }
        for(int i = 0; i < right-left;i++){
            ListNode temp = pre.next;
            pre.next = temp.next;
            // temp.next = pre;
            // tail.next = temp;
            temp.next = tail.next;
            tail.next = temp;
        }

        return dummyhead.next;
    }
}

参考来源：

【1】代码随想录 Carl 链表

【2】leetcode 木已成舟 Java-双指针-头插法

原文链接：https://blog.csdn.net/weixin_45532984/article/details/125388968