力扣面试常见150题:栈+链表(java+c++)

栈

有效的括号(20)

���定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"输出：true

示例 2：

输入：s = "()[]{}"输出：true

示例 3：

输入：s = "(]"输出：false

提示：

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

  两数相加(2)

  给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

  请你将两个数相加，并以相同形式返回一个表示和的链表。

  你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

  示例 1：

  输入：l1 = [2,4,3], l2 = [5,6,4]输出：[7,0,8]解释：342 + 465 = 807.

  示例 2：

  输入：l1 = [0], l2 = [0]输出：[0]

  示例 3：

  输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]输出：[8,9,9,9,0,0,0,1]

  提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 val : 0;//同上 int c = tmp1 + tmp2 + jin;//进位加上这两个数之和 if(!res){//结果链表为空 res = cur = new ListNode(c % 10);//结果为和的个位数 } else{//结果链表不为空 cur->next = new ListNode(c % 10);//当前结点为和的个位数 cur = cur->next; } jin = c / 10;//进位数 if(l1){//l1不为空 l1 = l1->next; } if(l2){ l2 = l2->next; } } if(jin > 0){//最后的进位大于0，则加到最后 cur->next = new ListNode(jin); } return res; }};

    //java版，击败100%/** * 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 addTwoNumbers(ListNode l1, ListNode l2) {        ListNode res = null, cur = null;        int jin = 0;        while(l1 != null || l2 != null){            int tmp1 = l1 != null ? l1.val : 0;            int tmp2 = l2 != null ? l2.val : 0;            int c = tmp1 + tmp2 + jin;            if(res == null){                res = cur = new ListNode(c % 10);            }            else{                cur.next = new ListNode(c % 10);                cur = cur.next;            }            jin = c / 10;            if(l1 != null){                l1 = l1.next;            }            if(l2 != null){                l2 = l2.next;            }        }        if(jin > 0){            cur.next = new ListNode(jin);        }        return res;    }}

    合并两个有序链表(21)

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

    示例 1：

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

    示例 2：

    输入：l1 = [], l2 = []输出：[]

    示例 3：

    输入：l1 = [], l2 = [0]输出：[0]

    提示：

    • 两个链表的节点数目范围是 [0, 50]
    • -100 next = list1; list1 = list1->next; } else{ cur->next = list2; list2 = list2->next; } cur = cur->next; } cur->next = list1 ? list1 : list2; return res->next; }};

      //java版打败100%/** * 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 mergeTwoLists(ListNode list1, ListNode list2) {        ListNode res = new ListNode(-1), cur = res;//初始化，定义结果链表和当前链表        while(list1 != null && list2 != null){            if(list1.val  Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。 
      返回复制链表的头节点。
       
      用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
       

      • val：一个表示 Node.val 的整数。
      • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

        你的代码 只 接受原链表的头节点 head 作为传入参数。

        示例 1：

        输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

        示例 2：

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

        示例 3：

        输入：head = [[3,null],[3,0],[3,null]]输出：[[3,null],[3,0],[3,null]]

        提示：

        • 0 next]; map[cur] -> random = map[cur -> random]; cur = cur ->next; } return map[head]; }};class Solution {public: Node* copyRandomList(Node* head) { unordered_map node_map; Node* p = head; while (p) { if (!node_map.count(p)) {//哈希表里面没有当前结点p Node* t = new Node(p->val); node_map[p] = t;//哈希表插入值为val的结点 } Node* n = node_map[p];//插入val值后的结点 if (p->next) {//插入next if (!node_map.count(p->next)) { Node* t = new Node(p->next->val); node_map[p->next] = t; } n->next = node_map[p->next]; } if (p->random) {//插入random if (!node_map.count(p->random)) { Node* t = new Node(p->random->val); node_map[p->random] = t; } n->random = node_map[p->random]; } p = p->next; } return node_map[head]; }};//高效写法class Solution {public: unordered_map origin2new; Node* copyRandomList(Node* head) { if(!head){ return NULL; } if(origin2new.find(head) == origin2new.end()){ Node *newHead = new Node(head -> val); origin2new[head] = newHead; newHead -> next = copyRandomList(head -> next); newHead -> random = copyRandomList(head -> random); } return origin2new[head]; }};

          //java/*// Definition for a Node.class Node {    int val;    Node next;    Node random;    public Node(int val) {        this.val = val;        this.next = null;        this.random = null;    }}*/class Solution {    public Node copyRandomList(Node head) {        if(head == null){            return null;        }        Node cur = head;        Map m = new HashMap();        while(cur != null){            m.put(cur, new Node(cur.val));            cur = cur.next;        }        cur = head;//复制val后重来插入next和random        while(cur != null){            m.get(cur).next = m.get(cur.next);            m.get(cur).random = m.get(cur.random);            cur = cur.next;        }        return m.get(head);    }}

          反转链表(206)

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

          示例 1：

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

          示例 2：

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

          示例 3：

          输入：head = []输出：[]

          提示：

          • 链表中节点的数目范围是 [0, 5000]
          • -5000 next = prev; prev = curr; curr = next; } return prev; }};

            /** * 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 prev = null; //前指针节点        ListNode curr = head; //当前指针节点        //每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移        while (curr != null) {            ListNode nextTemp = curr.next; //临时节点，暂存当前节点的下一节点，用于后移            curr.next = prev; //将当前节点指向它前面的节点            prev = curr; //前指针后移            curr = nextTemp; //当前指针后移        }        return prev;    }}

            反转链表II(92)

            给你单链表的头指针 head 和两个整数 left 和 right ，其中 left next;//cur2下一个结点指向 pre->next = cur2;//pre下一个结点指向cur2 } return res->next; }};class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { // 设置 dummyNode 是这一类问题的一般做法 ListNode dummyNode = new ListNode(-1); dummyNode.next = head; ListNode pre = dummyNode; for (int i = 0; i

            法二:运用反转链表的方法class Solution {private:    void reverseLinkedList(ListNode *head) {        // 也可以使用递归反转一个链表        ListNode *pre = nullptr;        ListNode *cur = head;        while (cur != nullptr) {            ListNode *tmp = cur->next;            cur->next = pre;            pre = cur;            cur = tmp;        }    }public:    ListNode *reverseBetween(ListNode *head, int left, int right) {        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论        ListNode *dummyNode = new ListNode(-1);        dummyNode->next = head;        ListNode *pre = dummyNode;        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点        // 建议写在 for 循环里，语义清晰        for (int i = 0; i next;        }        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点        ListNode *rightNode = pre;        for (int i = 0; i next;        }        // 第 3 步：切断出一个子链表（截取链表）        ListNode *leftNode = pre->next;        ListNode *curr = rightNode->next;        // 注意：切断链接        pre->next = nullptr;        rightNode->next = nullptr;        // 第 4 步：同第 206 题，反转链表的子区间        reverseLinkedList(leftNode);        // 第 5 步：接回到原来的链表中        pre->next = rightNode;        leftNode->next = curr;        return dummyNode->next;    }};class Solution {    public ListNode reverseBetween(ListNode head, int left, int right) {        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论        ListNode dummyNode = new ListNode(-1);        dummyNode.next = head;        ListNode pre = dummyNode;        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点        // 建议写在 for 循环里，语义清晰        for (int i = 0; i  
            删除链表的倒数第N个结点(19)
             
            给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
             
            示例 1：
              
            输入：head = [1,2,3,4,5], n = 2输出：[1,2,3,5]
             
            示例 2：
             
            输入：head = [1], n = 1输出：[]
             
            示例 3：
             
            输入：head = [1,2], n = 1输出：[1]
             
            提示：
             

            • 链表中结点的数目为 sz
            • 1 next; delete res; return res2; }};//c++击败100%的写法class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0); dummy -> next = head; ListNode* p = dummy; ListNode* q = dummy; while(n--){ q = q -> next; } while(q -> next){ p = p -> next; q = q -> next; } p -> next = p -> next -> next; ListNode* ans = dummy -> next; delete dummy; return ans; }};

              /** * 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) {        int cnt = 0;        ListNode len = head;        while(len != null){            cnt++;            len = len.next;        }        int m = cnt - n;        ListNode res = new ListNode(0, head);        ListNode cur = res;        for(int i = 1; i  
              删除排序链表中的重复元素II(82)
               
              给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
               
              示例 1：
                
              输入：head = [1,2,3,3,4,4,5]输出：[1,2,5]
               
              示例 2：
                
              输入：head = [1,1,1,2,3]输出：[2,3]
               
              提示：
               

              • 链表中节点数目在范围 [0, 300] 内
              • -100 next->next != NULL){//cur下一个和下下一个都不空 if(cur->next->val == cur->next->next->val){//先两个对比 int x = cur->next->val;//相同值 while(cur->next != NULL && cur->next->val == x){//往后比较 cur->next = cur->next->next;//跳过 } } else{ cur = cur->next; } } return res->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 ListNode deleteDuplicates(ListNode head) {        if (head == null) {            return head;        }                ListNode dummy = new ListNode(0, head);        ListNode cur = dummy;        while (cur.next != null && cur.next.next != null) {            if (cur.next.val == cur.next.next.val) {                int x = cur.next.val;                while (cur.next != null && cur.next.val == x) {                    cur.next = cur.next.next;                }            } else {                cur = cur.next;            }        }        return dummy.next;    }}

                旋转链表(61)

                给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

                示例 1：

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

                示例 2：

                输入：head = [0,1,2], k = 4输出：[2,0,1]

                提示：

                • 链表中节点的数目在范围 [0, 500] 内
                • -100 next = head;//成环 while(m--){ cur = cur->next;//根据移动次数往后遍历 } ListNode* res = cur->next;//结果链表的头结点 cur->next = NULL;//尾结点next为空 return res; }};

                  class Solution {    public ListNode rotateRight(ListNode head, int k) {        if (k == 0 || head == null || head.next == null) {            return head;        }        int n = 1;        ListNode iter = head;        while (iter.next != null) {            iter = iter.next;            n++;        }        int add = n - k % n;        if (add == n) {            return head;        }        iter.next = head;        while (add-- > 0) {            iter = iter.next;        }        ListNode ret = iter.next;        iter.next = null;        return ret;    }}

                  分隔链表(86)

                  给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

                  你应当 保留 两个分区中每个节点的初始相对位置。

                  示例 1：

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

                  示例 2：

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

                  提示：

                  • 链表中节点的数目在范围 [0, 200] 内
                  • -100