# 链表

## 单链表的反转

给定一个单链表的头 head，完成链表的逆序调整

![image-20211230130842084](/files/DiBwK7j06cVnmBzGWmVu)

将原链表从Head开始取出（原链表指针为head，新链表指针为newHead），一次添加到新链表的Head上即可完成逆序操作。代码如下：

```java
// 单链表
static class SingleNode {
  int data;
  SingleNode next;

  SingleNode(int data) {
    this.data = data;
  }
}

// 返回一个SingleNode，防止逆序之后头结点不可达，造成jvm垃圾回收
public SingleNode reverseSingle(SingleNode head) {
  if (head == null) {
    return head;
  }
  SingleNode newHead = null;
  SingleNode next;
  while (head != null) {
    next = head.next;
    head.next = newHead;
    newHead = head;
    head = next;
  }
  return newHead;
}

@Test
public void testReverseSingle() {
  SingleNode head = new SingleNode(1);
  head.next = new SingleNode(2);
  head.next.next = new SingleNode(3);

  // 链表反转
  head = reverseSingle(head);
  Assert.assertEquals(head.data, 3);
  Assert.assertEquals(head.next.data, 2);
  Assert.assertEquals(head.next.next.data, 1);

  // 打印
  while (head != null) {
    System.out.println(head.data);
    head = head.next;
  }
}
```

> 更简单的理解方式：所有箭头方向调换

## 双链表的反转

![image-20211230141458348](/files/I2tiPSt2dkmDH1QrDvEX)

如上图所示，双链表的反转比单链表更简单，只需要将上述所有元素的next指针与last指针指向的元素完全互相调换即可，代码如下：

```java
static class DoubleNode {
  int data;
  DoubleNode next;
  DoubleNode last;

  public DoubleNode(int data) {
    this.data = data;
  }
}

public void reverseDouble(DoubleNode head) {
  DoubleNode next = null;
  while (head != null) {
    next = head.next;
    head.next = head.last;
    head.last = next;
    head = head.last; // 因为元素调换，所以这里不是next而是last
  }
}

@Test
public void testReverseDouble() {
  DoubleNode node1 = new DoubleNode(1);
  DoubleNode node2 = new DoubleNode(2);
  DoubleNode node3 = new DoubleNode(3);
  node1.next = node2;
  node2.next = node3;
  node2.last = node1;
  node3.last = node2;

  // 链表反转
  reverseDouble(node1);
  Assert.assertEquals(node3.next, node2);
  Assert.assertEquals(node2.next, node1);
  Assert.assertNull(node1.next);

  Assert.assertNull(node3.last);
  Assert.assertEquals(node2.last, node3);
  Assert.assertEquals(node1.last, node2);
}
```

## 删除单链表指定的值

```java
public SingleNode4Delete deleteNode(SingleNode4Delete head, int num) {
  // 先找到头结点，也就是第一个不是3的节点
  while (head != null && head.value == 3) {
    head = head.next;
  }

  // 指针向后移动
  //      如果当前为3，那么就将指针前一个节点指向指针后一个节点
  //      如果当前不为3，cur就继续移动
  SingleNode4Delete pre = head;
  SingleNode4Delete cur = head.next;
  while (cur != null) {
    if (cur.value != num) {
      pre = cur;
    } else {
      pre.next = cur.next;
    }
    cur = cur.next;
  }
  return head;
}
```

## K个节点的组内逆序调整

```
假设有一个有序链表：
1 2 3 4 5 6 7 8
要求3个节点内的组内逆序调整，结果为：
3 2 1 6 5 4 7 8 
不够一组的不做逆序调整，比如上述案例中的7和8
```

LeetCode： [25. K 个一组翻转链表 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/)

> 链表问题画图处理

我自己的解法：

```java
public ListNode reverseKGroup(ListNode head, int k) {
  if (head == null || k < 2) {
    return head;
  }

  ListNode thisGroupLastNode = null;
  ListNode preGroupLastNode = null;
  ListNode next;
  ListNode newHead = null;
  ListNode groupNewHead = null;
  int count = k;
  while (count > 0) {
    ListNode h = head;
    for (int i = 0; i < k - 1; i++) {
      if (h.next == null) {
        h = null;
        break;
      }
    }
    // 循环退出条件2
    // 如果head == null ， 或者他下面的 k - 1 个next为空
    // 那么就退出循环，不做逆序处理。并将剩下的部分与上组结尾想连接
    if (h == null) {
      if (thisGroupLastNode != null) {
        thisGroupLastNode.next = head;
      }
      break;
    }

    // 新组的第一次循环
    // thisGroupLastNode 变为上一组的最后一个节点 preGroupLastNode
    // 当前节点为 thisGroupLastNode，当前最的最后一个节点，备份该节点，防止逆序后找不到
    if (count == k) {
      preGroupLastNode = thisGroupLastNode;
      thisGroupLastNode = head;
    }

    // 第一组的最后一次循环，那么head就是这个链表的开始位置
    if (count == 1 && newHead == null) {
      newHead = head;
    }

    // 这组的最后一次循环，那么该节点就是与上一组的尾节点相连接的节点，对节点连接
    if (count == 1) {
      if (preGroupLastNode != null) {
        preGroupLastNode.next = head;
      }
    }

    // 交换组内节点
    next = head.next;
    head.next = groupNewHead;
    groupNewHead = head;
    head = next;


    if (count == 1) {
      // 并重置count，再次完成k-1个循环
      count = k;
      continue;
    }

    count--;

  }
  return newHead;
}

@Test
public void testReverseKGroup() {
  ListNode head = new ListNode(1);
  head.next = new ListNode(2);
  head.next.next = new ListNode(3);
  head.next.next.next = new ListNode(4);
  head.next.next.next.next = new ListNode(5);


  ListNode node = reverseKGroup(head, 2);
  System.out.println(node);
}
```

## 两个链表相加

给定两个链表的头结点head1和head2，认为从左到右是某个数字从低位到高位，返回相加之后的链表。例子：

```
4 -> 3 -> 6    =>  634
2 -> 5 -> 3    =>  253
==> 
634 + 253 = 986
故返回的新链表为：  6 -> 8 -> 9

3 -> 4 -> 6 -> 1  => 1643 
7 -> 9 -> 7       => 797
1643 + 797 = 2440
故返回的新链表为：  0 -> 4 -> 4 -> 2
```

**解析**，可以用加法的竖式来完成这个功能：

```
  1643
x  797
-------
  2440
```

循环遍历链表，分为两个阶段：

1. 在短链表内范围的数字相加，注意记录进位信息
2. 在短链表外，长链表内的数字相加，注意处理进位信息
3. 处理溢出的进位

代码如下：

```java
static class PlusNode {
  private int value;
  PlusNode next;

  public PlusNode(int value) {
    if (value < 0 || value > 9) {
      throw new IllegalArgumentException();
    }
    this.value = value;
  }

  public int getValue() {
    return value;
  }

  public void setValue(int value) {
    this.value = value;
  }
}

/**
 * 两个链表相加 加法竖式处理
 * 备注：也可以使用字符串
 */
public PlusNode plusLinkedList(PlusNode head1, PlusNode head2) {
  // 1. 找到长链表与短链表
  int node1Size = getPlusNodeSize(head1);
  int node2Size = getPlusNodeSize(head2);
  PlusNode l = node1Size > node2Size ? head1 : head2;
  PlusNode s = node1Size > node2Size ? head2 : head1;

  // 2. 第一阶段：循环短链表的次数，将数字依次相加，并记录进位信息
  PlusNode curL = l; // 长链表循环指针
  PlusNode curS = s; // 短链表循环指针
  int carry = 0;// 表示进位信息， 0 表示没有进位
  int curSum = 0; // 当前的长链表指针与短链表指针的所指向的val的和
  PlusNode lastLNode = curL; // 记录最后一个元素，用于添加溢出的最后一个进位
  while (curS != null) {
    curSum = curL.getValue() + curS.getValue();
    carry = curSum / 10;
    curL.setValue(curSum % 10);
    lastLNode = curL;
    curL = curL.next;
    curS = curS.next;
  }
  // 3. 第二阶段：循环长链表多出的那部分长度，并处理进位信息\
  while (curL != null) {
    curSum = carry + curL.getValue();
    carry = curSum / 10;
    curL.setValue(curSum % 10);
    lastLNode = curL;
    curL = curL.next;
  }

  // 4. 第三阶段：处理溢出的最后一个进位
  if (carry > 0) {
    lastLNode.next = new PlusNode(carry);
  }

  return l;
}

private int getPlusNodeSize(PlusNode node) {
  int count = 0;
  while (node != null) {
    count++;
    node = node.next;
  }
  return count;
}

@Test
public void testPlusLinkedList() {
  PlusNode head1 = new PlusNode(4);
  head1.next = new PlusNode(3);
  head1.next.next = new PlusNode(6);

  PlusNode head2 = new PlusNode(2);
  head2.next = new PlusNode(5);
  head2.next.next = new PlusNode(3);

  PlusNode node = plusLinkedList(head1, head2);
  Assert.assertNotNull(node);
  Assert.assertEquals(node.getValue(), 6);
  Assert.assertEquals(node.next.getValue(), 8);
  Assert.assertEquals(node.next.next.getValue(), 9);


  head1 = new PlusNode(0);
  head1.next = new PlusNode(0);
  head1.next.next = new PlusNode(5);

  head2 = new PlusNode(0);
  head2.next = new PlusNode(0);
  head2.next.next = new PlusNode(5);

  node = plusLinkedList(head1, head2);
  Assert.assertNotNull(node);
  Assert.assertEquals(node.getValue(), 0);
  Assert.assertEquals(node.next.getValue(), 0);
  Assert.assertEquals(node.next.next.getValue(), 0);
  Assert.assertEquals(node.next.next.next.getValue(), 1);
}
```

## 两个有序链表的合并

给定两个有序链表头节点 head1和head2，返回合并之后的大链表，要求依然有序。例子：

```
1 -> 3 -> 3 -> 5 -> 7
2 -> 2 -> 3 -> 3
合并：
1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 3 -> 5 -> 7
```

思路：

1. 找到较小的头部，那么这个链表就是主链表，也就是新链表的头
2. 两个指针 cur1 和 cur2，cur1指向主链表头部，cur2 指向副链表头部
3. 移动cur1
   1. 如果cur1的新值小于cur2所处的位置，继续移动cur1
   2. 如果cur1的新值大于cur2所处的位置，将cur2所处元素插入到cur1，并移动cur2指针到链表的下个位置
4. 当cur1移动到尾部时，将cur2剩余节点全部拼接到主链表中，链表的合并已经完成
5. 当cur2移动到尾部时，链表的合并已经完成

代码：

```java
static class UnionNode {
  int value;
  UnionNode next;

  public UnionNode(int value) {
    this.value = value;
  }
}

public UnionNode unionNode(UnionNode head1, UnionNode head2) {
  if (head1 == null || head2 == null || head1 == head2) {
    return head1 != null ? head1 : head2;
  }
  UnionNode main = head1.value <= head2.value ? head1 : head2; // 主链表指针cur1
  UnionNode cur1 = main.next; // 主链表指针cur1
  UnionNode cur2 = head1.value <= head2.value ? head2 : head1;  // 副链表指针cur2
  UnionNode cur2Next; // 记录副链表指针的下一个元素用于添加元素后继续循环副链表
  UnionNode cur1Pre = main; // 记录主链表的上一个元素，用于拼接新的元素
  while (cur1 != null && cur2 != null) {
    if (cur1.value <= cur2.value) {
      // 如果cur1的新值小于cur2所处的位置，继续移动cur1
      cur1Pre = cur1;
      cur1 = cur1.next;
    } else {
      // 如果cur1的新值大于cur2所处的位置，将cur2所处元素插入到cur1，并移动cur2指针到链表的下个位置
      cur2Next = cur2.next;
      cur1Pre.next = cur2;
      cur2.next = cur1;
      cur1Pre = cur2;
      cur2 = cur2Next;
    }
  }
  // 当cur1移动到尾部时，将cur2剩余节点全部拼接到主链表中，链表的合并已经完成
  if (cur1 == null) {
    cur1Pre.next = cur2;
  }
  return main;
}

@Test
public void testUnionNode() {
  UnionNode head1 = new UnionNode(1);
  head1.next = new UnionNode(3);
  head1.next.next = new UnionNode(3);
  head1.next.next.next = new UnionNode(5);
  head1.next.next.next.next = new UnionNode(7);

  UnionNode head2 = new UnionNode(2);
  head2.next = new UnionNode(2);
  head2.next.next = new UnionNode(3);
  head2.next.next.next = new UnionNode(3);

  UnionNode node = unionNode(head1, head2);
  Assert.assertNotNull(node);
  int[] resultArr = {1, 2, 2, 3, 3, 3, 3, 5, 7};
  int count = 0;
  while (node != null) {
    Assert.assertEquals(node.value, resultArr[count]);
    node = node.next;
    count++;
  }

}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yangsx95.gitbook.io/notes/computer-science/shu-ju-jie-gou-he-suan-fa/lian-biao.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.