代码随想录--链表

链表

理论基础

�index.php/tags-41973.html" >�表分为几种类型：

• 单链表

  // 定义链表--javapublic class ListNode{// 结点的值int val;// 下一个结点    ListNode next;    // 节点的构造函数(无参)    public ListNode() {    }    // 节点的构造函数(有一个参数)    public ListNode(int val) {        this.val = val;    }    // 节点的构造函数(有两个参数)    public ListNode(int val, ListNode next) {        this.val = val;        this.next = next;    }}

  • 双链表
  • 循环链表

    存储方式

    在内存中不是连续分布的，而是散乱分布在内存中的某地址上。

    移除链表元素

    方法1：迭代

    （）
    1. 分析头节点即为需要删除元素
    2. 删除头节点后，判断链表是否为空
    3. 不为空，则利用一个临时指针来遍历链表，删除元素

    class Solution {    public ListNode removeElements(ListNode head, int val) {        // 删除头结点        while (head != null && head.val == val){            head = head.next;        }        if (head == null)  return head;        // 删除后续结点        ListNode cur = head;        while(cur.next != null){            if (cur.next.val == val){                cur.next = cur.next.next;            }else {                cur = cur.next;            }        }        return head;    }}

    方法2：递归

    class Solution {    public ListNode removeElements(ListNode head, int val) {       if(head==null)           return null;        head.next=removeElements(head.next,val);        if(head.val==val){            return head.next;        }else{            return head;        }    }}

    设计链表

    实现 MyLinkedList 类：

    • MyLinkedList() 初始化 MyLinkedList 对象。
    • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
    • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
    • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
    • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
    • void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

      思路

      1. 首先需要定义结点（代码中提供的是链表的创建，不是结点的定义，不要混淆）
      2. 再分别设计不同方法

         单链表

      // 定义结点class ListNode{    int val;    ListNode next;    public ListNode(int val){        this.val = val;    }}// 链表定义class MyLinkedList {    // 记录链表中结点数量    int size;    ListNode head;    public MyLinkedList() {        size = 0;        head = new ListNode(0);    }        public int get(int index) {        if (index = size){            return -1;        }        ListNode cur = head;        for (int i = 0; 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  size){            return;        }        index = Math.max(0, index);        size++;        ListNode pred = head;        for (int i = 0; i = size){            return;        }        size--;        ListNode cur = head;        for (int i = 0; i  
      双链表
       

      • 实现双向链表，即每个节点要存储本身的值，后继节点和前驱节点。
      • 除此之外，需要一个哨兵节点作为头节点 head 和一个哨兵节点作为尾节点 tail。
      • 仍需要一个 size参数保存有效节点数。

        【注意】双链表遍历下标为index的时候，要考虑是从前还是从后开始遍历

        class MyLinkedList {    int size;    ListNode head;    ListNode 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 = size) {            return -1;        }        ListNode curr;        if (index + 1 = size) {            return;        }        ListNode pred, succ;        if (index  
        翻转链表
         
        方法一：迭代
         
        class Solution {    public ListNode reverseList(ListNode head) {        ListNode pre = null, curr = head;        while(curr != null) {            ListNode next = curr.next;            curr.next = pre;            pre = curr;            curr = next;        }        return pre;    }}
         
        方法二：递归
        假设链表的其余部分已经被反转了
         
        class Solution {    public ListNode reverseList(ListNode head) {        if (head == null || head.next == null) {            return head;        }        ListNode newHead = reverseList(head.next);        /**        第一轮出栈  head=5 head.next为空 返回5        第二轮出栈  head=4 head.next=5 head.next.next=5.next=head=4  4.next=null        ......        同上述          */        head.next.next = head;        head.next = null;        return newHead;    }}
         
        两两交换链表中的节点
         
        方法一：迭代
         
        class Solution {    public ListNode swapPairs(ListNode head) {        ListNode tempNode = new ListNode(0);        tempNode.next = head;        ListNode temp = tempNode;        while( temp.next != null && temp.next.next != null){            ListNode node1 = temp.next;            ListNode node2 = temp.next.next;            temp.next = node2;            node1.next = node2.next;;            node2.next = node1;            temp = node1;        }        return tempNode.next;    }}
         
        方法二：递归
         
        class Solution {    public ListNode swapPairs(ListNode head) {        if (head == null && head.next == null ){            return head;        }        ListNode newHead = head.next;        head.next = swapPairs(newHead.next);        newHead.next = head;        return newHead;    }}
         
        删除链表的倒数第N个节点
         
        思路
         
        利用快慢指针，两个指针相差n+1个结点，最后，快指针到链表末端的时候，慢指针指向需要删除的结点的前一个结点
         
        class Solution {    public ListNode removeNthFromEnd(ListNode head, int n) {         ListNode newHead = new ListNode(0);        newHead.next = head;        ListNode fast = newHead, slow = newHead;        for(int i = 0; i            fast = fast.next;        }        while(fast != null){            fast = fast.next;            slow = slow.next;        }        slow.next = slow.next.next;        return newHead.next;    }}    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        ListNode curA = headA, curB = headB;        int lenA = 0, lenB = 0;        while(curA != null){            lenA++;            curA = curA.next;        }        while(curB != null ){            lenB++;            curB = curB.next;        }        curA = headA;        curB = headB;        if (lenA             for(int i = 0; i