LeetCode——链表

链表

链表类型：单链表（只有next指针）、双链表（pre指针和next指针）、循环链表（尾节点指向头节点）

增、删、改、遍历、翻转、交换

1.设计链表707中等

class LinkedNode {
    int val;
    LinkedNode next;
    public LinkedNode() {

    }
    public LinkedNode(int val) {
        this.val = val;
    }
}
class MyLinkedList {
    // 链表的长度
    private int size;
    // 链表的虚拟头节点和虚拟尾节点
    private LinkedNode head;


    public MyLinkedList() {
        size = 0;
        head = new LinkedNode(0);
    }
    
    public int get(int index) {
        if (index >= size) {
            return -1;
        }
        LinkedNode cur = head.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        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;
        }
        size++;
        LinkedNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        LinkedNode newNode = new LinkedNode(val);
        newNode.next = cur.next;
        cur.next = newNode;

    }
    
    public void deleteAtIndex(int index) {
        // 检查要插入元素索引的范围
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        LinkedNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
    }
}

2.移除链表元素

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 定义虚拟头节点
        ListNode newhead = new ListNode(0, head);
        // pre表示前一个元素，为了删除元素后可以把链表串起来
        ListNode pre = newhead;
        // 循环链表的节点，判断该节点的值是否与val相等
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                // cur = cur.next;
                // pre.next = cur;
                pre.next = cur.next;
            } else {
                pre = pre.next;
                // cur = cur.next;
            }
            cur = cur.next;
        }
        return newhead.next;
    }
}

3.删除链表的倒数第N个结点

//  // 先实现，写两次遍历，第一次记录链表的结点总个数，第二次删除；这里要防止第一次遍历结束后还能找到头
// class Solution {
//     public ListNode removeNthFromEnd(ListNode head, int n) {
//         // 第一次遍历
//         ListNode newhead = new ListNode (-1, head);
//         ListNode cur = head;
//         int count = 0;
//         // 第一次遍历
//         while (cur != null) {
//             count += 1;
//             cur = cur.next;
//         }
//         // 第二次遍历
//         // num记录要从前往后遍历到第几个位置
//         int num = count - n;
//         ListNode now = newhead;
//         while (num > 0) {
//             now = now.next;
//             num -= 1;
//         }
//         now.next = now.next.next;
//         return newhead.next;
//     }
// }


// // 双指针，快慢指针，第一个指针先走n步，第二个指针留在初始位置，那么当第一个位置走到链表尾部的时候，第二个指针就处在在删除的节点位置(如果加上虚拟头节点，就是走在了要删除节点的前一个节点上)
// class Solution {
//     public ListNode removeNthFromEnd (ListNode head, int n) {
//         // 定义一个虚拟头节点
//         ListNode newhead = new ListNode(-1, head);
//         // 定义第一个节点
//         ListNode first = head;
//         // 定义第二个节点
//         ListNode second = newhead;
//         int i = 0;
//         while (i < n) {
//             i ++;
//             first = first.next;
//         }
//         while (first != null) {
//             first = first.next;
//             second = second.next;
//         }
//         // 删除节点
//         second.next = second.next.next;
//         return newhead.next;
//     }
// }


// 栈
class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // 定义虚拟头节点
        ListNode newhead = new ListNode (-1, head);
        // 定义栈
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = newhead;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; i ++) {
            stack.pop();
        }
        // stack.peek()检索到栈顶元素并获取到，但是不会被删除
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        return newhead.next;
    }
}

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

重点是要一直链起来，不要忽略某个步骤断掉链表

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 定义一个虚拟头节点
        ListNode newhead = new ListNode(-1, head);
        // 一个节点一个节点进行遍历
        ListNode cur = newhead;
        while (cur.next != null && cur.next.next != null) {
            ListNode bef = cur.next;
            ListNode aft = cur.next.next;
            // 交换
            cur.next = aft;  // 链住
            bef.next = aft.next;  // 交换
            aft.next = bef;
            cur = bef;

        }
        return newhead.next;
    }
}

5.相交链表160简单

// class Solution {
// public:
//     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//         // 使用哈希表存储节点。首先遍历链表A，将A中的节点存入哈希表，遍历链表B，如果B中的节点在哈希表中，之后的所有节点都要在hash表中；如果不在，继续遍历B的下一个节点
//         // 定义以节点为元素的hash表
//         unordered_set<ListNode *> visited;
//         ListNode *temp = headA;
//         while (temp != nullptr) {
//             visited.insert(temp);
//             temp = temp -> next;
//         }
//         temp = headB;
//         while (temp != nullptr) {
//             if (visited.count(temp)) {
//                 return temp;
//             }
//             temp = temp -> next;
//         }
//         return nullptr;
//     }
// };


class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 双指针，利用相遇的时候两个指针应该走过一样的步数
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA;
        ListNode *pB = headB;
        while (pA != pB) {
            if (pA == nullptr) {
                pA = headB;
            } else {
                pA = pA->next;
            }
            if (pB == nullptr) {
                pB = headA;
            } else {
                pB = pB->next;
            }
        }
        return pB;
    }
};

【未完待续……】

总结：

如果由遍历且修改的需求，虚拟头接带你好使

链表要链起来始终

找规律，有没有简单实现的方法，例如反转链表，是不是头插法就很合适

思想：双指针！排序的话归并！