08-链表

学习链表几个方法

1. 学会画图，通过图像来比较方便地理解内容
2. 可以使用虚拟的头结点，这样可以减少一部分边界情况
3. 可以使用临时节点，这样可以防止链表断开，减少思考步骤

题目

LC2. 两数相加

思路：

1. 观察题目，发现这个题目不是正序的，而是逆序（从小到大）的，因此不需要翻转列表
2. 遍历列表，从末尾开始，用 t 来存储两个链表相加的值，然后创建一个新的节点，把个位数的值给加进去。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode head = new ListNode(-1), cur = head;
	int t = 0;
	while (l1 != null || l2 != null || t != 0) {
		if (l1 != null) {
			t += l1.val;
			l1 = l1.next;
		}
		if (l2 != null) {
			t += l2.val;
			l2 = l2.next;
		}

		cur.next = new ListNode(t % 10);
		cur = cur.next;
		t /= 10;
	}

	return head.next;
}

LC24. 两两交换链表中的节点

这个就要用到我之前说的内容了：

1. 创建虚拟头结点
2. 画图来思考，尤其是遇到空指针的时候
3. 创建临时的节点

public ListNode swapPairs(ListNode l) {
	if (l == null || l.next == null) return l;
	ListNode head = new ListNode(-1);
	head.next = l;

	// 定义四个指针
	ListNode c1 = head, c2 = c1.next, c3 = c2.next, c4 = c3.next;

	while (true) {
		c1.next = c3;
		c3.next = c2;
		c2.next = c4;
		if (c4 == null || c4.next == null) break;
		c1 = c2;
		c2 = c1.next;
		c3 = c2.next;
		c4 = c3.next;
	}

	return head.next;
}