链表反转

LeetCode 206 反转链表

题目非常的简单，就是给一个链表，把它反转过来，head变成last，last变成head。

如果不熟悉链表的数据结构，硬做也不是不行，遍历链表得到一个数组，反转数组，然后重建链表。这也不是不能过，但肯定是倒数解法。

链表的反转是非常标准的操作。

头插法

这个做法的核心是：每次拿到一个节点，都设置当前节点位链表的new head。

伪代码说明；

声明pre、concurrent节点，pre节点为空，concurrent节点等于head
循环concurrent，如果concurrent为空那么终止循环
- 声明next用于临时保存concurrent.next
- 设置concurrent节点的next节点为pre（反转concurrent）
- 移动pre节点的位置：pre = concurrent;
- 移动concurrent节点的位置：concurrent = next
循环结束，返回pre节点就是反转后的head位置

递归

递归的思路很好理解，就是一直往下找到最后一个节点，反转最后一个点，并且把反转之后的结果返回

伪代码说明：

如果当前节点为空或者当前节点的下一个节点为空，那么无需执行反转操作，直接返回
向下递归，递归返回的结果是当前节点的next，也就是下面示例中的B
将当前节点的下一个节点的下一个节点设置为当前节点，也就是： A->B->C 变化为B->C->A->B的环
然后断开环，设置当前节点的next为空，B->C->A->B转化成 C->A->B
返回变化后的新的头节点。

使用栈

栈的特点是后进先出，如果我们从头遍历链表，head节点会最后出栈，那么只需要两次循环，就能反转重建链表。

伪代码说明：

遍历把链表中的所有节点压入栈
从栈中取出数据重建链表

所有代码

public class Solution {

  public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
      ListNode next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
    return prev;
  }

  public ListNode reverseListDFS(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode newHead = reverseListDFS(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
  }

  public ListNode reverseListUsingStack(ListNode head) {
    if (head == null) {
      return null; // 如果链表为空，直接返回null
    }

    Stack<ListNode> stack = new Stack<>();
    ListNode current = head;

    // 遍历链表并将节点压入栈中
    while (current != null) {
      stack.push(current);
      current = current.next;
    }
    // 弹出栈中节点并重新连接
    ListNode newHead = stack.pop(); // 新的头节点是栈顶元素
    current = newHead;
    while (!stack.isEmpty()) {
      current.next = stack.pop(); // 将下一个节点设为栈顶元素
      current = current.next;
    }
    current.next = null; // 最后一个节点的 next 设为 null

    return newHead; // 返回新的头节点
  }
}

链表合并

LeetCode 21合并两个有序链表

这个有两个典型思路

迭代

我觉得迭代的思路有点动态规划的感觉，核心只有一句：两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。

比较简单清晰（出差间隙真的好累）就省略伪代码。

遍历

遍历的思路就是人脑直观思考的结果。

我每次检查两个链表的头节点，谁小就把谁放到新的链表中，同时把值比较小的节点往后推一位。

唯一需要注意的是，通过返回ans.next省略头节点处理。

代码

public class Solution {

  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode ans = new ListNode(-1);
    ListNode concurrent = ans;
    while (list1 != null && list2 != null) {
      if (list1.val <= list2.val) {
        concurrent.next = list1;
        list1 = list1.next;
      } else {
        concurrent.next = list2;
        list2 = list2.next;
      }
      concurrent = concurrent.next;
    }
    concurrent.next = list1 == null ? list2 : list1;

    return ans.next;
  }

  //两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
  public ListNode mergeTwoListsDFS(ListNode list1, ListNode list2) {
    if (list1 == null) {
      return list2;
    } else if (list2 == null) {
      return list1;
    } else if (list1.val < list2.val) {
      list1.next = mergeTwoListsDFS(list1.next, list2);
      return list1;
    } else {
      list2.next = mergeTwoListsDFS(list1, list2.next);
      return list2;
    }
  }
}