链表

203.移除链表元素

题意：删除链表中等于给定值 val 的所有节点。

示例 1：输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

示例 2：输入：head = [], val = 1 输出：[]

示例 3：输入：head = [7,7,7,7], val = 7 输出：[]

解答：

/**
 * 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 ListNode removeElements(ListNode head, int val) {
        while(head != null && head.val == val){
            head = head.next;
        }
        ListNode node = head;
        while(node != null && node.next != null){
            if(node.next.val == val){
                node.next = node.next.next;
            } else{
                node = node.next;
            }
        }
        return head;
    }
}

//设置一个虚拟头结点：
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode();
        dummy.next = head; //虚拟头结点
        ListNode node = dummy;
        while(node.next != null){
            if(node.next.val == val){
                node.next = node.next.next;
            } else{
                node = node.next;
            }
        }
        return dummy.next;
    }
}

707.设计链表

力扣题目链接

题意：

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

解答：

//单链表
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 MyLinkedList {
    int size;
    ListNode head;
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }
    
    public int get(int index) {
        if(index < 0 || index > size-1){
            return -1;
        }
        ListNode cur = head;
        while(index > 0){
            cur = cur.next;
            index--;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        if(size == 0){
            head.val = val;
            size++;
            return;
        }
        ListNode dummy = new ListNode(val);
        dummy.next =head;
        head = dummy;
        size++;
    }
    
    public void addAtTail(int val) {
        if(size == 0){
            addAtHead(val);
            return;
        }
        ListNode cur = head;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = new ListNode(val);
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next =head;
        ListNode cur = dummy;
        if(index == size){
            addAtTail(val);
        } else if(index > size){
        } else{
            while(index > 0){
                cur = cur.next;
                index--;
            }
            ListNode temp = new ListNode(val);
            temp.next = cur.next;
            cur.next = temp;
            size++;
        }
        head = dummy.next;

    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index > size-1){
            return;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;

        while(index > 0){
            cur = cur.next;
            index--;
        }
        cur.next = cur.next.next;
        head = dummy.next;
        size--;
    }
}

//双链表
class ListNode{
    int val;
    ListNode next,prev;
    ListNode(){}
    ListNode(int val){
        this.val = val;
    }
    ListNode(int val,ListNode prev,ListNode next){
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}
class MyLinkedList {
    int size;
    ListNode head,tail;

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
        tail = new ListNode(0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int index) {
        if(index < 0 || index > size-1){
            return -1;
        }
        ListNode cur = this.head;
        if(index < size/2){

            for(int i = 0;i <= index;i++){
                cur = cur.next;
            }
        }else{
            cur = this.tail;
            for(int i = size;i > index;i--){
                cur = cur.prev;
            }
            
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index < 0 || index > size){
            return;
        }
        ListNode cur = this.head;
        for(int i = 0;i < index;i++){
            cur = cur.next;
        }
        ListNode temp = new ListNode(val);
        cur.next.prev = temp;
        temp.prev = cur;
        temp.next = cur.next;
        cur.next = temp;
        size++;

    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index > size-1){
            return;
        }
        ListNode cur = this.head;
        for(int i = 0;i < index;i++){
            cur = cur.next;
        }
        cur.next.next.prev = cur;
        cur.next = cur.next.next;
        size--;
    }
}

206.反转链表

力扣题目链接

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

解答：

//双指针
/**
 * 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 ListNode reverseList(ListNode head) {
        ListNode first = head;
        ListNode second = null;
        ListNode pre = null;
        while(first != null){
            second = first.next;
            first.next = pre;
            pre = first;
            first = second;
        }
        return pre;
    }
}

//递归
/**
 * 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 ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }
    public ListNode reverse(ListNode pre,ListNode first){
        if(first == null){
            return pre;
        }
        
        ListNode second = first.next;
        first.next = pre;
        return reverse(first,second);
        
    }
}

// 从后向前递归
/**
 * 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 ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode last = reverseList(head.next);//翻转第二个节点之后的节点
        head.next.next = head;
        head.next = null;
        return last;
    }
}

24. 两两交换链表中的节点

力扣题目链接

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解答：

/**
 * 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 ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode cur = head;
        head = cur.next;
        ListNode temp = null;
        ListNode pre = null;
        while(cur != null && cur.next != null){
            if(pre != null){
                pre.next = cur.next;//步骤一，可以使用虚拟头节点，就可以避免判断
            }
            temp = cur.next.next;
            cur.next.next = cur;//步骤二
            cur.next = temp;//步骤三，交换步骤二和三可以不用加temp节点
            pre = cur;
            cur = temp;
        }
        return head;
    }
}
//递归
/**
 * 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 ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode cur = head;
        head = cur.next;
        ListNode last = swapPairs(cur.next.next);
        cur.next.next = cur;
        cur.next = last;
        return head;
    }
}

19.删除链表的倒数第N个节点

力扣题目链接

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

解答：

/**
 * 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 ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        ListNode temp = cur;

        for(int i = 0;i < n;i++){
            temp = temp.next;
        }
        while(temp.next != null){
            cur = cur.next;
            temp = temp.next;
        }
        cur.next = cur.next.next;
        return dummy.next;
    }
}

面试题 02.07. 链表相交

同：160.链表相交

力扣题目链接

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

解答：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        int cur = 1;
        int size = 0;
        ListNode temp = null;
        while(A != null){
            size++;
            A = A.next;
        }
        while(cur <= size && B != null){
            A = headA;
            B = headB;
            for(int i = 0;i < size - cur;i++){
                A = A.next;
            }
            while(B != null){
                if(B == A){
                    cur++;
                    temp = A;
                    break;
                }
                B = B.next;
            }
        }
        return temp;
    }
}//另一种方法是同步移动

//合并链表实现同步移动
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        while(A != B){
            if(A == null){
                A = headB;
            } else{
                A = A.next;
            }
            if(B == null){
                B = headA;
            } else{
                B = B.next;
            }
        }
        return A;
    }
}

142.环形链表II

力扣题目链接

题意：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

解答：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        boolean iscircle = false;
        while(fast != null && fast.next != null && slow.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                iscircle =true;
                break;
            }
        }
        if(iscircle == false) return null;
        ListNode temp = fast;
        fast = fast.next;
        slow =head;
        while(temp != slow){
            while(temp != fast){
                if(fast ==slow){
                    return slow;
                } else{
                    fast = fast.next;
                }
            }
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

//秒解
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                slow = head;
                while(slow != fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

203.移除链表元素​

707.设计链表​

206.反转链表​

24. 两两交换链表中的节点​

19.删除链表的倒数第N个节点​

面试题 02.07. 链表相交​

142.环形链表II​

总结​

203.移除链表元素

707.设计链表

206.反转链表

24. 两两交换链表中的节点

19.删除链表的倒数第N个节点

面试题 02.07. 链表相交

142.环形链表II

总结