q206_反转链表
思路1，双指针法，或者叫迭代法
动画题解
代码
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
复杂度分析
时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。
空间复杂度：O(1)。
思路2，递归法
图解
代码
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode listNode = reverseList(head.next);
head.next.next = head;
head.next = null;
return listNode;
}
递归代码中，最不好理解的是
head.next.next = head;
查看以上的图解过程，当 1（head） 后面的表完成反转后，2 同时被 1 和 3指向，这是要做的是把2指向1，把1指向null。结合图解，多看几遍，还是比较容易理解的。
复杂度分析
时间复杂度：O(n)，假设 n 是列表的长度，那么时间复杂度为 O(n)。
空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。
q2_两数相加
思路1，递归
从链表第一位开始相加，并增加一个boolean参数，表示是否加1。当两个链表都为空时，结束递归。
代码
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
return addTwoNumbers2(l1, l2, false);
}
public ListNode addTwoNumbers2(ListNode l1, ListNode l2, boolean add1) {
int val;
if (l1 == null && l2 == null) {
if (add1) {
return new ListNode(1);
} else {
return null;
}
} else if (l1 == null) {
val = l2.val + (add1 ? 1 : 0);
} else if (l2 == null) {
val = l1.val + (add1 ? 1 : 0);
} else {
val = l1.val + l2.val + (add1 ? 1 : 0);
}
add1 = val >= 10;
val = val % 10;
ListNode res = new ListNode(val);
res.next = addTwoNumbers2(l1 == null ? null : l1.next, l2 == null ? null : l2.next, add1);
return res;
}
执行结果
思路2
迭代，预先指针
过程和图解
小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。
代码
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode tem = pre;
int tag = 0;
while (l1 != null || l2 != null) {
int a = l1 == null ? 0 : l1.val;
int b = l2 == null ? 0 : l2.val;
int sum = a + b + tag;
tag = sum / 10;
sum %= 10;
tem.next = new ListNode(sum);
tem = tem.next;
if (l1 != null)
l1 = l1.next;
if (l2 != null)
l2 = l2.next;
}
if (tag > 0) {
tem.next = new ListNode(tag);
}
return pre.next;
}
q148_排序链表
思路1
把链表转成list，list排序后，生成新的链表
代码
public ListNode sortList(ListNode head) {
List<Integer> list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
Collections.sort(list);
ListNode last = null;
for (int i = list.size() - 1; i >= 0; i--) {
int v = list.get(i);
ListNode listNode = new ListNode(v);
listNode.next = last;
last = listNode;
}
return last;
}
需要额外的空间
思路2
q19_删除链表的倒数第N个节点
思路1
双指针，预先指针
代码
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre = new ListNode(0);
pre.next = head;
ListNode right = pre;
ListNode left = pre;
for (int i = 0; i <= n; i++) {
right = right.next;
}
while (right != null) {
right = right.next;
left = left.next;
}
left.next = left.next.next;
return pre.next;
}
q61_旋转链表
思路
把单链表转成环，然后再在合适的地方解环
代码
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
ListNode t = head;
int len = 1;
while (t.next != null) {
t = t.next;
len++;
}
t.next = head;
k = len - k % len;
ListNode t2 = head;//新的链尾，t2的next才是新的head，所以要-1
for (int i = 0; i < k - 1; i++) {
t2 = t2.next;
}
ListNode ans = t2.next;
t2.next = null;
return ans;
}
需要注意的是解环的位置，应该是长度len减去 k%len
q138_复制带随机指针的链表
思路1
map+递归
从链表头开始复制，用map<oldnode,newnode>存数据，当需要复制的节点不存在，构建新的，当节点已经存在，从map获取
代码
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
if (map.containsKey(head)) {
return map.get(head);
}
Node node = new Node(head.val);
map.put(head, node);
node.next = copyRandomList(head.next);
node.random = copyRandomList(head.random);
return node;
}
思路2
详见图解解法1
优秀图解
代码
public Node copyRandomList2(Node head) {
if (head == null) {
return null;
}
//第一步，在每个原节点后面创建一个新节点
Node tem = head;
while (tem != null) {
Node t = new Node(tem.val);
t.next = tem.next;
tem.next = t;
tem = tem.next.next;
}
//第二步，设置新节点的随机节点
tem = head;
while (tem != null) {
if (tem.random != null) {
tem.next.random = tem.random.next;
}
tem = tem.next.next;
}
//第三步，将两个链表分离
Node dummy = new Node(-1);
tem = head;
Node cur = dummy;
while (tem != null) {
cur.next = tem.next;
cur = cur.next;
tem.next = cur.next;
tem = tem.next;
}
return dummy.next;
}