LeetCode链表常用技巧(一)

链表遍历

单链表中的每个结点不仅包含值，还包含链接到下一个结点的地址。通过这种方式，单链表将所有结点按顺序组织起来。所以我们对链表的遍历可以通过两种方式：迭代或者递归

我们约定链表结构如下：

复制代码

	public class ListNode {
	int val;
	ListNode next;
	ListNode() {}
	ListNode(int val) { this.val = val; }
	ListNode(int val, ListNode next) { this.val = val; this.next = next; }
	}

迭代遍历代码：

复制代码

	public void list(ListNode head){
	if(head == null){
	return;
	}
	while(head != null){
	System.out.println(head);
	head = head.next;
	}
	}

递归遍历

复制代码

	public void list(ListNode head){
	if(head == null){
	return;
	}
	System.out.println(head);
	list(head.next);
	}

链表部分反转

LeetCode92题： 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

我们先考虑反转整个链表，然后一步一步推导出反转链表部分。

对于整个链表的反转我们有两种方式，迭代或者递归

复制代码

	//迭代
	public ListNode reverse(ListNode head){
	if(head == null || head.next == null){//当链表为空或者只有一个元素的时候
	return head;
	}
	//pre为当前节点前一个节点，当前节点，next下一个节点
	ListNode pre = null,cur = head,next = head;
	while(cur != null){
	next = cur.next;//获取当前节点下一个节点
	cur.next = pre;//将当前节点的下一个节点设置为前一个节点
	pre = cur;//将前一个节点后移
	cur = next; //当前节点后移
	}
	return pre;
	}
	//递归
	public ListNode reverse(ListNode head){
	if(head.next == null){
	return head;
	}
	ListNode last = reverse(head.next);//递归
	head.next.next = head;
	head.next = null;
	return last;
	}

反转链表的前k个节点

复制代码

	//递归反转单链表以head为头节点前k个
	ListNode successor = null;
	public ListNode reverseK(ListNode head,int k){
	if(k == 1){
	successor = head.next;
	return head;
	}
	ListNode last = reverseK(head.next,k-1);
	head.next.next = head;
	head.next = successor;
	return last;
	}

反转链表的一部分

复制代码

	public ListNode reverseBetween(ListNode head, int left, int right) {
	if(head == null || right - left == 0){
	return head;
	}
	ListNode cur = head;
	ListNode pre = null;
	for(int i = 1; i < left;i++){
	pre = cur;
	cur = cur.next;
	}
	if(pre == null){
	head = reverseK(head,right - left + 1);
	}else{
	pre.next = reverseK(cur,right - left + 1);
	}
	return head;
	}

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

复制代码

	//迭代遍历实现
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
	ListNode prehead = new ListNode(-1);//占位头指针，避免空指针
	ListNode cur = prehead;
	while(l1 != null && l2 != null){
	if(l1.val <= l2.val){
	cur.next = l1;
	l1 = l1.next;
	}else{
	cur.next = l2;
	l2 = l2.next;
	}
	cur = cur.next;
	}
	cur.next = l1 == null ? l2 : l1;
	return prehead.next;
	}
	//递归实现
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
	//递归实现
	if(l1 == null){
	return l2;
	}else if(l2 == null){
	return l1;
	}else if(l1.val <= l2.val){
	l1.next = mergeTwoLists(l1.next,l2);
	return l1;
	}else{
	l2.next = mergeTwoLists(l1,l2.next);
	return l2;
	}
	}