Java 刷题笔记——singly ListNode

Definition for singly-linked list.

public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
}

（图片来自https://www.cnblogs.com/ysocean/p/7928988.html）

• 生成新的ListNode:

ListNode a = new ListNode(int x);

这里的int x 为首节点的值，也可以为任何值，因为一般情况下我们不会用到单链表的首节点，它只是作为一个启动的功能。

• 填加节点

通常想要在首尾填加节点的话很简单。如果是开头，可以创建一个新的首节点并赋予它首节点的值，接着把next引向原链表即可。末尾填加值只需要直接next = 要加入的链表或创建新节点。下面是简单的示例：

// 开头填加
NodeList a;  // 原链表
NodeList b = new NodeList(int x); // x想要填加的初始值
b.next = a;  // 连接原链表
a = b;

//  结尾填加
NodeList a;
a.next = new NodeList(int x);

中间填加需要把链表断开插入新值再重新连接

注意点

1. 链表的可以使用栈（stack）的push() 和pop()方法来寄存和取出，通常用于翻转链表
2. 链表算法题返回时一般应返回值会从链表指向的那个值开始返回，而且每个实例变量的指向是不同的。例如：

ListNode a;  // 假设它的值为 1，2，3，4，5
ListNode b = a;
ListNode c = a;
a = a.next;
c = c.next.next;
return a;  // 返回值为2，3，4，5
return b;  // 返回值为1，2，3，4，5
return c;  // 返回值为3，4，5

所以我们一般会创建一个新的NodeList作return对象用