顺序表和链表面试题

顺序表

(1)原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。

oj链接
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

双指针

class Solution {public int removeElement(int[] nums, int val) {int left = 0;for (int right = 0; right < nums.length; right++) {if (nums[right] != val) {nums[left++] = nums[right];}}return left;}
}

(2)删除有序数组中的重复项

oj链接
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k

双指针

class Solution {public int removeDuplicates(int[] nums) {if(nums == null || nums.length == 0) return 0;int front = 0;int next = 1;while(next < nums.length){if(nums[front] != nums[next]){nums[++front] = nums[next];}next++;}return front+1;}
}

优化(相邻的元素不同不进行多余的赋值操作)
像[1,2,3,4,5]就不用进行赋值操作

class Solution {public int removeDuplicates(int[] nums) {if(nums == null || nums.length == 0) return 0;int front = 0;int next = 1;while(next < nums.length){if(nums[front] != nums[next]){if(next - front > 1){nums[front + 1] = nums[next];}front++;}next++;}return front + 1;}
}

(3)合并两个有序数组

oj链接
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

从后面开始确定

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {while(m>0&&n>0) {if(nums1[m-1]>nums2[n-1]) {nums1[m+n-1] = nums1[m-1];m--;} else {nums1[m+n-1] = nums2[n-1];n--;}}while(n>0) {nums1[n-1] = nums2[n-1];n--;}}
}

链表

(1)删除链表中等于给定值 val 的所有节点

oj链接
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

class Solution {public ListNode removeElements(ListNode head, int val) {while(head!=null&&head.val==val) {head= head.next;}if(head == null) {return null;}ListNode prev = head;while(prev.next!=null) {if(prev.next.val==val) {prev.next=prev.next.next;} else {prev=prev.next;}}return head;}
}

(2)反转一个单链表

oj链接
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

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

递归

class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;}
}

(3) 合并两个有序链表

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

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode prehead = new ListNode(-1);ListNode prev = prehead;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {prev.next = l1;l1 = l1.next;} else {prev.next = l2;l2 = l2.next;}prev = prev.next;}prev.next = l1 == null ? l2 : l1;return prehead.next;}
}

递归

class Solution {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;}}
}

(4)链表的中间结点

oj链接
给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

快慢指针

慢指针走一步,快指针走两步

while循环条件不能换顺序

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

(5)链表中倒数第k个结点

牛客网链接
输入一个链表，输出该链表中倒数第k个结点。

public class Solution {public ListNode FindKthToTail(ListNode head,int k) {ListNode fast = head;ListNode slow = head;if(k<=0||head==null) return null;while(k-1>0) {if(fast.next == null) return null;fast = fast.next;k--;}while(fast.next!= null) {fast = fast.next;slow = slow.next;}return slow;}
}

(6)分割链表

oj链接
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

class Solution {public ListNode partition(ListNode head, int x) {if(head==null) return null;ListNode less = new ListNode(-1);ListNode lessHead = less;ListNode larger = new ListNode(-1);ListNode largerHead = larger;while(head != null) {if(head.val<x) {less.next = head;less = less.next;} else {larger.next = head;larger = larger.next;}head = head.next;}larger.next = null;less.next = largerHead.next;return lessHead.next;}
}

方法二:

class Solution {public ListNode partition(ListNode head, int x) {ListNode cur = head;ListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;//使用cur来遍历 所有的节点while (cur != null) {if (cur.val < x) {if (bs == null) {bs = cur;be = cur;} else {be.next = cur;be = be.next;}} else {// >= xif (as == null) {as = cur;ae = cur;} else {ae.next = cur;ae = ae.next;}}cur = cur.next;}if (bs == null) {return as;}be.next = as;if (as != null) {ae.next = null;}return bs;}
}

如果bs为null,那么原链表最后一个节点(next是null)是ae,ae的next就不用置为null

(7)输入两个链表，找出它们的第一个公共结点(Y型)

oj链接
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode pA = headA, pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}
}

(8)给你一个链表的头节点 head ，判断链表中是否有环。

oj链接
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。
思路
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针走到链表的末尾。

为什么快指针每次走两步，慢指针走一步可以？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可
能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动
一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，
快指针肯定是可以追上慢指针的，即相遇。

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

(9)给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

oj链接
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。
思路
设链表头部走x步到环的入口， 环有 y 个节点(包括环入口节点)
先跟上一题一样, fast走两步,slow走一步,如果有环的话在环中相遇.
设在环中走了s步(不包括环的入口节点)
那么slow走了x+s步
fast走了x+s+ny(n是圈数)
因为fast走的距离是slow的两倍
所以2(x+s) = x+s+ny
即x=(n-1)*y+(y-s)
让fast从起始位置走,slow从相遇的位置走(n-1)*y+y-s步,他们会在环的入口相遇.

public class Solution {public ListNode detectCycle(ListNode head) {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 fast;}}return null;}
}

(10)判定链表是否是回文

即正读和倒读一样的链表
牛客网链接
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
思路
先用快慢指针找到中间节点(奇数中间,偶数第二个中间结点),将中间节点之后的节点反转,一头从头结点,一头从末尾结点开始比较.

奇数的情况

当两个指针相遇的时候返回true

偶数的情况

当第一个节点的下一个节点是第二个节点且相等就返回true

public class PalindromeList {public boolean chkPalindrome(ListNode A) {if(A==null) {return true;}ListNode fast = A;ListNode slow = A;while(fast!=null&&fast.next!=null) {fast = fast.next.next;slow = slow.next;}ListNode prev = slow;ListNode cur =slow.next;while(cur!=null) {ListNode next = cur.next;cur.next = prev;prev = cur;cur = next;}while(A!=slow) {if(A.val!=prev.val) {return false;}//偶数的情况if(A.next==prev) {return true;}A=A.next;prev=prev.next;}return true;}
}