算法总结（三) 链表

链表相关的题目

这里用来记录链表相关的题目以及思路

相交链表

输入两个链表，找出它们的第一个公共结点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
        定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
        两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
        **/
        if(headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
        while(pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

K个一组翻转链表

思路：每k个翻转一次，可以单独进行反转，但注意上一组的尾节点和下一组的头节点要连接起来，所以需要记录上一组尾节点。

   public static ListNode reverseKGroup(ListNode head, int k) {
	ListNode start = head;
	ListNode end = teamEnd(start, k);
	if (end == null) {
		return head;
	}
	// 第一组很特殊因为牵扯到换头的问题
	head = end;
	reverse(start, end);
	// 翻转之后start变成了上一组的结尾节点
	ListNode lastTeamEnd = start;
	while (lastTeamEnd.next != null) {
		start = lastTeamEnd.next;
		end = teamEnd(start, k);
		if (end == null) {
			return head;
		}
		reverse(start, end);
		lastTeamEnd.next = end; // 上一组结尾节点要连接下一组头节点
		lastTeamEnd = start;
	}
	return head;
}

// 当前组的开始节点是s，往下数k个找到当前组的结束节点返回
public static ListNode teamEnd(ListNode s, int k) {
	while (--k != 0 && s != null) {
		s = s.next;
	}
	return s;
}

// s -> a -> b -> c -> e -> 下一组的开始节点
// 上面的链表通过如下的reverse方法调整成 : e -> c -> b -> a -> s -> 下一组的开始节点
public static void reverse(ListNode s, ListNode e) {
	e = e.next;
	ListNode pre = null, cur = s, next = null;
	while (cur != e) {
		next = cur.next;
		cur.next = pre;
		pre = cur;
		cur = next;
	}
	s.next = e;
}

随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

思路：将每个节点复制一份，并把复制的节点放在原节点后面，比如1->2->3->4->5，复制之后变成1->1’->2->2’->3->3’->4->4’->5->5’，然后遍历链表，将复制的节点的random指针指向原节点的random指针指向的节点的下一个节点。最后将链表拆分，返回新链表的头节点。

public Node copyRandomList(Node head) {
    Node pre =head;
    Node next = null;
    if(head == null){
        return null;
    }
    //将链表复制串联
    while(pre != null){
        next = pre.next;
        pre.next = new Node(pre.val);
        pre.next.next = next;
        pre = next;
    }
    //将random进行复制
    pre = head;
    while(pre!=null){
        next = pre.next.next;
        pre.next.random = pre.random == null ? null : pre.random.next;
        pre = next;
    }
    //分离两个链表
    Node newHead = head.next;
    Node newPre = newHead;
    pre =head;
    while(pre != null){
        next = pre.next.next;
        newPre.next = next == null ? null : next.next ;
        pre.next = next;
        pre =next;
        newPre = newPre.next;
    }
    return newHead;
}

判断回文链表

思路：利用快慢指针，找到中点，然后翻转后半部分链表，比较前后两个链表是否相等。最后恢复链表。

public boolean isPalindrome(ListNode head) {
    if(head == null) return false;
    if(head.next==null) return true;
    //利用快慢指针找到中点
    ListNode man = head;
    ListNode kuai = head;
    while (kuai.next != null && kuai.next.next != null) {
        man = man.next;
        kuai = kuai.next.next;
    }
    ListNode reverseHead = reverseList(man);
    Boolean isPal = true;
    ListNode reversePre =reverseHead;
    ListNode pre = head;
    while(reversePre!=null && pre!=null){
        if(pre.val!=reversePre.val){
            isPal = false;
            break;
        }
        reversePre = reversePre.next;
        pre = pre.next;
    }
    //链表还原
    reverseList(reverseHead);
    return isPal;
}

public ListNode reverseList(ListNode head){
    ListNode pre = null,next=null;
    while(head!=null){
        next =head.next;
        head.next = pre;
        pre =head;
        head = next;
    }
    return pre;
}

链表是否存在环 并求环的入口节点

思路：利用快慢指针，快指针每次移动两步，慢指针每次移动一步，如果快慢指针相遇，则说明链表有环，否则没有环。相遇的时候，快指针回到头节点，慢指针继续移动，但是慢指针和快指针每次都移动一步，再次相遇的时候就是环的入口节点。 a+(nb+c) = 2(a+c) a = nb - c 所以慢指针再走a步，就能到达入口节点。此时快指针也走a步，慢指针和快指针相遇的节点就是入口节点。

public static ListNode detectCycle(ListNode head) {
    if(head ==null){
        return null;
    }
    ListNode fast =head;
    ListNode slow = head;
    while(fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
        if(fast==slow){
            fast = head;
            while(fast!=slow){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }
    return null;
}

排序链表

要求：时间复杂度nlog(n),空间复杂度O(1)，且稳定
思路：利用非递归版本的归并排序，并且merge是合并两个有序链表。
代码很复杂，看看就好

   // 时间复杂度O(n*logn)，额外空间复杂度O(1)，有稳定性
// 注意为了额外空间复杂度O(1)，所以不能使用递归
// 因为mergeSort递归需要O(log n)的额外空间
public static ListNode sortList(ListNode head) {
	int n = 0;
	ListNode cur = head;
	while (cur != null) {
		n++;
		cur = cur.next;
	}
	// l1...r1 每组的左部分
	// l2...r2 每组的右部分
	// next 下一组的开头
	// lastTeamEnd 上一组的结尾
	ListNode l1, r1, l2, r2, next, lastTeamEnd;
	for (int step = 1; step < n; step <<= 1) {
		// 第一组很特殊，因为要决定整个链表的头，所以单独处理
		l1 = head;
		r1 = findEnd(l1, step);
		l2 = r1.next;
		r2 = findEnd(l2, step);
		next = r2.next;
		r1.next = null;
		r2.next = null;
		merge(l1, r1, l2, r2);
		head = start;
		lastTeamEnd = end;
		while (next != null) {
			l1 = next;
			r1 = findEnd(l1, step);
			l2 = r1.next;
			if (l2 == null) {
				lastTeamEnd.next = l1;
				break;
			}
			r2 = findEnd(l2, step);
			next = r2.next;
			r1.next = null;
			r2.next = null;
			merge(l1, r1, l2, r2);
			lastTeamEnd.next = start;
			lastTeamEnd = end;
		}
	}
	return head;
}

// 包括s在内，往下数k个节点返回
// 如果不够，返回最后一个数到的非空节点
public static ListNode findEnd(ListNode s, int k) {
	while (s.next != null && --k != 0) {
		s = s.next;
	}
	return s;
}

public static ListNode start;

public static ListNode end;

// l1...r1 -> null : 有序的左部分
// l2...r2 -> null : 有序的右部分
// 整体merge在一起，保证有序
// 并且把全局变量start设置为整体的头，全局变量end设置为整体的尾
public static void merge(ListNode l1, ListNode r1, ListNode l2, ListNode r2) {
	ListNode pre;
	if (l1.val <= l2.val) {
		start = l1;
		pre = l1;
		l1 = l1.next;
	} else {
		start = l2;
		pre = l2;
		l2 = l2.next;
	}
	while (l1 != null && l2 != null) {
		if (l1.val <= l2.val) {
			pre.next = l1;
			pre = l1;
			l1 = l1.next;
		} else {
			pre.next = l2;
			pre = l2;
			l2 = l2.next;
		}
	}
	if (l1 != null) {
		pre.next = l1;
		end = r1;
	} else {
		pre.next = l2;
		end = r2;
	}
}