JavaSE_05_顺序表与链表

遍历解法

class Solution {public ListNode deleteDuplicates(ListNode head) {if(head == null){return head;}ListNode pre = head;while(pre.next != null){if(pre.val == pre.next.val){pre.next = pre.next.next;}else{pre = pre.next;}}return head;}
}

递归解法

class Solution {public ListNode deleteDuplicates(ListNode head) {if(head == null){return head;}head.next = deleteDuplicates(head.next);if(head.next == null){return head;}if(head.val == head.next.val){head = head.next;return head;}else{return head;}}
}

解法一：三指针

class Solution {public ListNode deleteDuplicates(ListNode head) {if(head == null || head.next == null){return head;}ListNode dummyHead = new ListNode();dummyHead.next = head;ListNode pre = dummyHead, cur = pre.next, next = cur.next;while(next != null){if(cur.val != next.val){    //cur为不重复元素，三指针后移一位，将cur收入pre,pre管着所有不重复出现的节点pre.next = cur;pre = pre.next;cur = cur.next;next = next.next;}else{    //cur为重复元素，让next一直后移，直到next指向null或cur和next的值不相同，此时删除cur到next前一个节点，让cur指向next,next指向next的下一位，重复判断cur和next是否相等。while(next != null && cur.val == next.val){next = next.next;}if(next == null){pre.next = null;return dummyHead.next;}cur = next;next = next.next;}}//最后剩下一个链表最末尾的cur没有判断，将cur直接连接到pre后面pre.next = cur;return dummyHead.next;}
}

三指针精简版

/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
//用pHead这一个指针分类重复元素和非重复元素，用tail接受非重复元素。
public class Solution {public ListNode deleteDuplication(ListNode pHead) {ListNode dummyHead = new ListNode(-1);ListNode tail = dummyHead;while(pHead != null){if(pHead.next == null || pHead.val != pHead.next.val){tail.next = pHead;tail = pHead;}while(pHead.next != null && pHead.val == pHead.next.val){pHead = pHead.next;}pHead = pHead.next;}tail.next = null;return dummyHead.next;}
}

解法二：递归

class Solution {public ListNode deleteDuplicates(ListNode head) {if(head == null || head.next == null){return head;}//双指针找到不是重复节点的新头ListNode pre = head, cur = head.next;while(cur != null){if(cur.val != pre.val){head = pre;head.next = deleteDuplicates(head.next);return head;}else{while(cur != null && cur.val == pre.val){cur = cur.next;}if(cur == null){return null;}pre = cur;cur = cur.next;}}//pre变为cur以后，若退出循环，则pre是一个没有被判断的节点，且不是重复元素，此时当前链表只有一个pre,返回它即可。return pre;}
}

快慢指针

引入两个引用，让一个引用先走或多走几步,这样两个指针的相对距离就固定了；或者让一个指针的速度比另一个指针快，这样两个指针走过的距离之差是线性增长的。

class Solution {public ListNode middleNode(ListNode head) {ListNode low = head, fast = head;while(fast != null && fast.next != null){fast = fast.next.next;low = low.next;}return low;}
}

解法一：一边读取链表的节点值，一边将其用头插入的方式存到新链表中,额外空间复杂度：O(N)

class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null){return head;}ListNode newHead = null;ListNode node = head;for(; node != null; node = node.next){ListNode newNode = new ListNode(node.val);newNode.next = newHead;newHead = newNode;}return newHead;}
}

解法二：不开辟新链表

解法三：递归

class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null){return head;}ListNode pre = null, cur = head;while(cur != null){ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}
}

//递归
class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null){return head;}ListNode node = head.next;;head.next = null;ListNode reHead = reverseList(node);node.next = head;return reHead;}
}

class Solution {public ListNode getKthFromEnd(ListNode head, int k) {//fast领先low k个步长int count = 0;for(ListNode node = head; node != null; node = node.next, count ++){}if(k < 1 || k > count){return null;    //表示k不符合题意}ListNode fast = head, low = head;for(int i = 0; i < k; ++i){fast = fast.next;    //先让fast走k步，这样fast-k始终是low}while(fast != null){fast = fast.next;low = low.next;    //保持k个步长的相对距离，两个指针同步走}return low;}
}

//O(N)额外空间复杂度：先得到反转链表，再一一对比
class Solution {public boolean isPalindrome(ListNode head) {if(head == null){return false;}ListNode newHead = reverseList(head);ListNode node1 = head;ListNode node2 = newHead;while(node1 != null && node2 != null){if(node1.val != node2.val){return false;}node1 = node1.next;node2 = node2.next;}return true;}public ListNode reverseList(ListNode head){ListNode newHead = null;ListNode cur = head;while(cur != null){ListNode node = new ListNode(cur.val);node.next = newHead;newHead = node;cur = cur.next;}return newHead;}
}

//O(1)额外空间复杂度：找中间节点+后半段反转
class Solution {public boolean isPalindrome(ListNode head) {//找中点、逆序、比较if(head.next == null){return true;}//找中点ListNode fast = head.next, low = head;while(fast != null && fast.next != null){fast = fast.next.next;low = low.next;}//从low.next->end逆序ListNode pre = null, cur = low.next;low.next = null;while(cur != null){ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}//head->low;pre->null遍历比较ListNode p1 = head, p2 = pre;while(p1 != null && p2 != null){if(p1.val != p2.val){return false;}p1 = p1.next;p2 = p2.next;}return true;}
}

//双指针+头插
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {//left和right从1开始编号ListNode dummyHead = new ListNode();dummyHead.next = head;ListNode pre = dummyHead;//pre从虚拟头节点出发，走left-1步到达left的前一个节点for(int i = 0; i < left - 1; ++i){pre = pre.next;}//cur节点一开始指向left位置，不断地把cur节点的下一个节点头插入，插入的位置总是pre.next，在将cur.next插入到pre.next前，开辟新节点保存cur.next的值，再把cur.next接到cur.next.next上，循环right - left次ListNode cur = pre.next;for(int i = 0; i < right - left; ++i){ListNode node = new ListNode(cur.next.val);cur.next = cur.next.next;node.next = pre.next;pre.next = node;}return dummyHead.next;}
}

//回溯法（较难理解）
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {//这个函数递归的思想就是把left->right区间整体前移，直到left==1时，变为反转前(right-left+1)个节点，前移的手段就是在递推过程中，外层函数的head.next指向内层函数的返回值if(left == 1){return reverseN(head,right);}head.next = reverseBetween(head.next, left - 1, right - 1);return head;}ListNode behind;    //behind表示right节点的下一个节点public ListNode reverseN(ListNode head, int n){if(n == 1){behind = head.next;return head;}ListNode next = head.next;    //
ListNode newHead = reverseN(head.next, n - 1);next.next = head;    //head.next = behind;    //
,从n==1时，开始回溯，真正发挥反转作用就是编号为
这三行代码,相当于在不断往newHead开头的链表尾插。return newHead;}
}

//双引用遍历
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1 == null && list2 == null){return null;}if(list1 == null){return list2;}if(list2 == null){return list1;}ListNode dummyHead = new ListNode();ListNode tail = dummyHead, p1 = list1, p2 = list2;while(p1 != null && p2 != null){if(p1.val <= p2.val){tail.next = p1;p1 = p1.next;}else{tail.next = p2;p2 = p2.next;}tail = tail.next;}if(p1 == null){tail.next = p2;}else{tail.next = p1;}return dummyHead.next;}
}
//递归
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1 == null && list2 == null){return null;}if(list1 == null){return list2;}if(list2 == null){return list1;}if(list1.val <= list2.val){list1.next = mergeTwoLists(list1.next, list2);return list1;}else{list2.next = mergeTwoLists(list2.next, list1);return list2;}}
}

class Solution {public ListNode partition(ListNode head, int x) {ListNode min = new ListNode();ListNode max = new ListNode();    //创建两个虚拟头节点存储大于等于和小于x的值ListNode smallTail = min, bigTail = max, node = head;while(node != null){if(node.val < x){smallTail.next = node;smallTail = smallTail.next;}else{bigTail.next = node;bigTail = bigTail.next;}node = node.next;}smallTail.next = max.next;    //合并两个链表bigTail.next = null;return min.next;}
}

相交指的是指向同一个引用，即从该相交节点往后都只有一条路径了

假如链表A的不相交部分长度为a,链表B的不相交部分长度为b,两个链表的相交部分长度为c(若不相交，则c为0)，那么a + c + b == b + c + a .用两个指针a,b分别从headA 和 headB开始遍历两个链表，两个指针同步前进，a走完链表A时，从headB开始走，b同理，则它们有两次机会可能走到同一个节点：

1.若a == b 且 c != 0,那么当两个指针走到一起时返回该指针；

2.若a != b,那么如果它们存在交点，一定会是一个指针先走过该交点。拿上图举例：指针a因为只用走两个节点就可以到交点，而指针b需要走过三个节点才能到，所以a和b第一次会错过；那么，为了让它们再有可能相遇，两个指针重走一遍对方走过的路，这样做是为了消除在走到交点前因为各自走过的路不一样长而产生的错位，这样一来两个指针走过的节点都是a + b + c,此时它们指向交点。若没有交点，则它们都指向null.

综上，让a,b遍历，它们相等（指向同一个节点）时停止遍历，返回任意一个指针。相等有两种可能：1.都指向null->没有交点；2.指向交点。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode a = headA, b = headB;while(a != b){a = a == null ? headB : a.next;b = b == null ? headA : b.next;}return a;}
}

public class Solution {public boolean hasCycle(ListNode head) {if(head == null || head.next == null){return false;}ListNode fast = head.next, low = head;while(fast != null && fast.next != null){if(fast == low){return true;}fast = fast.next.next;low = low.next;}return false;}
}

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head, low = head, p = head;if(head == null || head.next == null){return null;}while(fast != null && fast.next != null){fast = fast.next.next;low = low.next;if(fast == low){while(low != p){p = p.next;low = low.next;}return p;}}return null;}
}

class Solution {public ListNode reverseKGroup(ListNode head, int k) {if(head.next == null || k <= 1){return head;}//先来一轮k个节点的反转ListNode dummyHead = new ListNode();ListNode pre = null, cur = head, begin = head, end;for(int i = 1; i <= k; i++){ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}dummyHead.next = pre;    //确定最终返回的头节点begin.next = cur;    //将第一段反转，并与后续节点连接起来end = begin;    //end是上一段反转后的最后一个节点while(cur != null){ListNode node = cur;for(int i = 1; i <= k; i ++){if(node == null){return dummyHead.next;}node = node.next;}//找到下一段有k个节点可以反转pre = node;begin = cur;for(int i = 1; i <= k; i++){ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}end.next = pre;end = begin;}return dummyHead.next;}
}