1.找出两个链表的交点
160.intersection-of-two-linked-lists
Leetcode
找两个链表的相交节点，简单的很，直接暴力解法，双重遍历就完事了。
时间复杂度O(n^2)，这种解法属实憨逼，面试要是上来就这个解法你就已经结束了。
//2020年8月17日
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode a = headA;
ListNode b = headB;
while(headA!=null){
while(headB!=null){
if(headA == headB){
return headA;
}
headB = headB.next;
}
headA = headA.next;
headB = b;
}
return null;
}
}经过一番思考后,有了如下代码。
假设两个链表有相交的话，那么定有广义上的一个长链表，一个短链表，将指针置为两个链表的头部，当短链表遍历完，长链表没遍历完的时候，指向短链表的指针重新指向长链表的头部，如此往复循环。
这个是个什么原理呢？
我们将下图中(1 2节点段)称为A，(3 4 5节点段)称为 C， (8 6 7节点段)称为B，那么就有
A + C + B = B + C + A
也就是上文提到的短链表遍历完从另一个链表头开始遍历的原因，这么下去，总有一天，两个指针会相遇的。
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;
}
}
2.删除排序链表中的重复元素
83.remove-duplicates-from-sorted-list
Leetcode
看到这题的第一想法还是遍历，可能这就是笨比吧，下面解法的大致思路如下：
设置两个指针，一个旗标：
a指针指向head节点，b指针为a指针的next节点，如果b和a指针指向的节点的值相同，则a.next = b.next
否则a指针继续往前走。
//2020年8月18日
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode a = head;
int flag = 0;
while(a!=null){
ListNode b = a.next;
if(b == null) flag=0;
while(b!=null){
if(a.val == b.val){
a.next = b.next;
flag = 1;
}else{
flag = 0;
}
break;
}
if(flag != 1){
a = a.next;
}
}
return head;
}
}由于这个写法实在是太笨了，看了下别人的解法：
首先将问题简化,当链表为null或[1]的时候，直接返回head
当链表长度为2及以上的时候,我们就要获取当前节点的next节点与当前节点进行比较，相等的话就取后面的节点。
写的好乱，md
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}3.删除链表的倒数第N个节点
19.remove-nth-node-from-end-of-list
Leetcode
我一开始想的是快慢指针的方法，一个快指针先走n步，然后两个指针再同时走，直到快指针的next为空；
这样慢指针的next就是我们要删除的节点，这样做确实可以通过一些样例，但是遇到就一个节点或者[1,2,3,4] 删除倒数第4个节点这样的，这个方法就不行了。
经过一番思考和搜索，我找到了一个设置预先指针的方法，预先指针p的next指向head节点，快指针与慢指针同时从预先节点出发，最后返回p.next，这样就避免了要删除的节点就是慢指针指向的那个节点的情况。
//2020年8月19日
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode c = new ListNode(-1);
c.next = head;
ListNode a = c,b = c;
while(n != 0){
b = b.next;
n--;
}
while(b.next != null){
a = a.next;
b = b.next;
}
a.next = a.next.next;
return c.next;
}
}4.两两交换链表中的节点
24.swap-nodes-in-pairs
Leetcode
//2020年8月20日
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null) return head;
ListNode preNode = new ListNode(-1);
preNode.next = head;
ListNode c = preNode;
while(preNode.next != null && preNode.next.next != null){
ListNode a = preNode.next;
ListNode b = a.next;
preNode.next = b;
a.next = b.next;
b.next = a;
preNode = preNode.next.next;
}
return c.next;
}
}5.链表求和
445.add-two-numbers-ii
Leetcode
//2020年8月28日
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> s1 = new Stack();
Stack<Integer> s2 = new Stack();
Stack<Integer> res = new Stack();
ListNode p1 = l1,p2 = l2;
ListNode head = new ListNode(-1);
int mul = 0;
while(p1!=null){
s1.push(p1.val);
p1 = p1.next;
}
while(p2!=null){
s2.push(p2.val);
p2 = p2.next;
}
while(!s1.isEmpty() || !s2.isEmpty() || mul!=0){
int x = s1.isEmpty() ? 0 : s1.pop();
int y = s2.isEmpty() ? 0 : s2.pop();
int sum = x + y + mul;
ListNode node = new ListNode(sum % 10);
node.next = head.next;
head.next = node;
mul = sum / 10;
}
return head.next;
}
}6.回文链表
- Palindrome Linked List
Leetcode
不知道为啥，我总是能想出来这种拉跨的解法。
将链表中的值放到数组中，然后在数组的首尾设置指针，比较两个指针的值是否相等
但题中提出要求说：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
说实话，O(1)空间复杂度我觉着是可以做到的，大概也是用两个指针这样的，但是具体思路嘛....
参考了cyc的思路，解法应该是这样的：将链表对半切开，将后边一半反转，依次比较是否相等
这里就涉及到了三个操作，切开，反转，比较相等
把这个解放到后面了
//2020年9月1日
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
ListNode a = head;
ArrayList<Integer> arr = new ArrayList();
while(a != null){
arr.add(a.val);
a = a.next;
}
Object[] newArr = arr.toArray();
int len = newArr.length;
for(int i=0,j=len-1;i<j;i++,j--){
if((int)newArr[i] == (int)newArr[j]){
}else{
return false;
}
}
return true;
}
}public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) slow = slow.next; // 偶数节点，让 slow 指向下一个节点
cut(head, slow); // 切成两个链表
return isEqual(head, reverse(slow));
}
//切开
private void cut(ListNode head, ListNode cutNode) {
while (head.next != cutNode) {
head = head.next;
}
head.next = null;
}
//反转
private ListNode reverse(ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode nextNode = head.next;
head.next = newHead;
newHead = head;
head = nextNode;
}
return newHead;
}
//相等否
private boolean isEqual(ListNode l1, ListNode l2) {
while (l1 != null && l2 != null) {
if (l1.val != l2.val) return false;
l1 = l1.next;
l2 = l2.next;
}
return true;
}7.分隔链表
- Split Linked List in Parts
Leetcode
今天就先不写解析了，看剧了，半泽直树2第七集
//2020年9月2日
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
int len = 0;
ListNode countForList = root;
while(countForList != null){
len++;
countForList = countForList.next;
}
int group = len / k;
int mod = len % k;
ListNode[] result = new ListNode[k];
ListNode now = root;
for(int i=0;now!=null && i<k;i++){
result[i] = now;
int curSize = group + (mod-- > 0 ? 1 : 0);
for(int j = 0; j < curSize - 1;j++){
now = now.next;
}
ListNode next = now.next;
now.next = null;
now = next;
}
return result;
}
}8.链表元素按奇偶聚集
- Odd Even Linked List (Medium)
Leetcode
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
在不使用额外空间的情况下，使用双指针法构造两个链表（一个奇链表，一个偶链表），最后再将两个链表合并到一起。
大致的思路如下图：
最后再将奇链表和偶链表连接起来
odd.next = evenHead;
//2020年9月8日
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null) return null;
ListNode odd = head,even = head.next,evenHead = even;
while(even != null && even.next != null){
odd.next = odd.next.next;
odd = odd.next;
even.next = even.next.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
京公网安备 11010502036488号