链表常见问题

/**
 * 单链表数据结构
 */
class Node {
  int val;
  Node next;
  public Node(int val) {
    this.val = val;
  }
}

0x01 链表翻转

题目描述：

这道算法题，说直白点就是：如何让后一个节点指向前一个节点。

// 1.翻转链表
public static Node reverse(Node head) {
  Node res = null;
  while (head != null) {
    Node h = head.next;
    head.next = res;
    res = head;
    head = h;
  }
  return res;
}

0x02 两数相加

题目描述：

Leetcode:给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

// 2.链表相加
public static Node plus(Node l1, Node l2) {
  Node dummyHead = new Node(0);
  Node l3 = dummyHead;
  int carry = 0;
  while (l1 != null || l2 != null || carry > 0) {
    int val = carry;
    val = (l1 != null ? val + l1.val : val);
    val = (l2 != null ? val + l2.val : val);
    Node t = new Node(val > 9 ? val - 10 : val);
    l3.next = t;
    carry = val > 9 ? 1 : 0;
    l1 = l1 != null ? l1.next : null;
    l2 = l2 != null ? l2.next : null;
    l3 = t;
  }
  return dummyHead.next;
}

0x03 链表中倒数第k个节点

题目描述：

输入一个链表，输出该链表中倒数第k个结点。

问题分析：

链表中倒数第k个节点也就是正数第(L-K+1)个节点。

首先两个节点/指针，一个节点 node1 先开始跑，指针 node1 跑到 k-1 个节点后，另一个节点 node2 开始跑，当 node1 跑到最后时，node2 所指的节点就是倒数第k个节点也就是正数第(L-K+1)个节点。

// 3.链表中倒数第k个节点
public static Node findKFromEnd(Node head, int k) {
  Node node1 = head, node2 = head;
  int len = 0, index = k; // 链表长度
  while (node1 != null) {
    len++;
    node1 = node1.next;

    // 从 len = k -1 的位置开始,执行 K 次，
    if (index > 0) {
      index--;
    } else {
      node2 = node2.next;
    }
  }
  if (len == 0 || len < k) return null;
  return node2;
}

0x04 删除链表的倒数第N个节点

题目描述：

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

问题分析:

• 两次遍历法

首先我们将添加一个 哑结点(dummyHead)作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。在第一次遍历中，我们找出列表的长度 L。然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第 (L - n) 个结点那里。我们把第 (L - n)个结点的 next 指针重新链接至第 (L - n + 2)个结点，完成这个算法。

• 一次遍历法：

链表中倒数第N个节点也就是正数第(L-N+1)个节点。 定义两个节点 node1、node2;node1 节点先跑，node1节点 跑到第 n+1 个节点的时候,node2 节点开始跑.当node1 节点跑到最后一个节点时，node2 节点所在的位置就是第 （L-n ） 个节点（L代表总链表长度，也就是倒数第 n+1 个节点）。

// 4.删除链表的倒数第N个节点
public static Node deleteKFromEnd(Node head, int k) {
  Node dummyHead = new Node(0);
  dummyHead.next = head;
  int len = 0, index = k;
  Node p1 = head, p2 = dummyHead;
  while (p1 != null) {
    len++;
    p1 = p1.next;
    if (index > 0) {
      index--;
    } else {
      p2 = p2.next;
    }
  }
  if (len >= k && k > 0) {
    p2.next = p2.next.next;
  }
  return dummyHead.next;
}

0x05 合并两个有序的链表

题目描述：

输入两个单调递增的链表，输出两个链表合成后的链表，需要合成后的链表单调递增。

// 5.合并两个排序的链表
public static Node merge(Node head1, Node head2) {
  if (head1 == null) return head2;
  if (head2 == null) return head1;
  Node t = null;
  if (head1.val < head2.val) {
    t = head1;
    t.next = merge(head1.next, head2);
  } else {
    t = head2;
    t.next = merge(head1, head2.next);
  }
  return t;
}