经典数据结构题目-链表

Gg Code / 2024-01-15 / 原文

链表

707. 设计链表

解题思路
- 参考官方的单向链表，设置一个成员变量作为虚拟头节点，一个成员变量size保存有效节点数
代码

public MyLinkedList() {
  size = 0;
  head = new ListNode(0);
}


public int get(int index) {
  if (index < 0 || index >= size) {
    return -1;
  }
  // 借助虚拟头节点，可以较为方便地获取到index对应的节点
  ListNode cur = head;
  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 > size) {
      return;
    }
    index = Math.max(0, index);
    size++;
  	// 定位到插入位置的前一个元素
    ListNode pred = head;
    for (int i = 0; i < index; i++) {
      pred = pred.next;
    }
  	// 插入元素
    ListNode toAdd = new ListNode(val);
    toAdd.next = pred.next;
    pred.next = toAdd;
}

public void deleteAtIndex(int index) {
  if (index < 0 || index >= size) {
    return;
  }
  size--;
  // 定位到删除位置的前一个
  ListNode pred = head;
  for (int i = 0; i < index; i++) {
    pred = pred.next;
  }
  // 删除元素
  pred.next = pred.next.next;
}

206. 反转链表

解法一

思路
- 快慢指针进行遍历，快指针先存下当前节点的next，再将next指向slow的。两指针再一起往前移动
代码

    public ListNode reverseList(ListNode head) {
        ListNode fast = head;
        ListNode slow = null;
        while(fast != null){
            ListNode next = fast.next;  // 注意点一
            fast.next = slow;
            slow = fast;
            fast = slow;
        }
        return last;
    }

注意点
- 注意点一：操作链表时，修改next指针时，注意是否需要保存下来，防止找不到了

解法二

思路
- 使用递归
  - 终止条件。只剩下一个节点，节点为空
  - 递归参数。入参，需要反转的链表头；出参，反转后的头
  - 当前层处理。接入到反转后的链表尾，next指针指向空
代码

 public ListNode reverseList(ListNode head) {
   			// 终止条件
        if (head == null || head.next == null) return head;
   			// 递归
        ListNode p = reverseList(head.next);
   			// 当前层处理
        head.next.next = head;
        head.next = null;
        return p;
    }

92. 反转链表 II

解法一

思路
- 通过一次遍历，定位出反转开始和结束关键的四个节点
- 遍历的过程，对left和right区间的进行反转
- 最后再根据四个关键节点进行重新拼接

代码

    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 定位出四个关键节点
        ListNode leftBefore = null;
        ListNode leftNode = null;
        ListNode rightAfter = null;
        ListNode rightNode = head; // 注意点一

        // 定位四个关键节点同时进行反转
        ListNode fast = head;
        ListNode slow =null;
        int index = 1;
        while(index <= right){
            ListNode next = fast.next;
            // 记录下反转开始
            if(index == left){
                leftBefore = slow;
                leftNode = fast;
            }
            // 开始进行反转
            if(index >= left){
                fast.next = slow;
            }
            // 快慢指针移动
            slow = fast;
            fast = next;
            index ++;            
        }
        rightAfter = fast;
        rightNode = slow;

        // 四个关键节点进行重新拼接
        leftNode.next = rightAfter;
        if(leftBefore == null){ // 注意点二
            return rightNode;
        }
        leftBefore.next = rightNode;
        return head;
    }

注意点
- 注意点一：因为结果将rightNode作为头返回，当只有一个元素时且要进行反转时，需要将原头节点返回
- 注意点二：left从1开始时，会导致leftBefore为空

解法二

思路
- 递归
  - 终止条件。当left等于1时，以当前为头的N个元素进行反转即可。可参考反转链表题
  - 递归参数。入参，以下一个节点为头的链表，因为少了一个元素，反转的位置都减一。出参，反转后的链表头
  - 当前层处理。头的next指针指向新的链表头
代码

    ListNode afterN = null;

      public ListNode reverseBetween(ListNode head, int left, int right) {
          if(left == 1){
              return reverseN(head,right);
          }
          head.next = reverseBetween(head.next,left-1,right-1);
          return head;
      }

      public ListNode reverseN(ListNode head, int n){
          if(n == 1){
              afterN = head.next; //注意点一
              return head;
          }
          ListNode newHead = reverseN(head.next, n-1);
          head.next.next = head;
          head.next = afterN; 
          return newHead;
      }