跳转至

Day4 | Part2

约 243 个字 101 行代码 3 张图片 预计阅读时间 2 分钟

24. 两两交换链表中的节点

两两交换其中相邻的节点，并返回交换后链表的头节点

如图所示: example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy, curr = head;
        while(curr != null && curr.next != null) {
            prev.next = curr.next;
            curr.next = prev.next.next;
            prev.next.next = curr;
            prev = curr; curr = curr.next;
        }
        head = dummy.next;
        return head;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
ListNode* swapPairs(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* prev = dummy, * curr = head;
    while(curr && curr->next) {
        prev->next = curr->next; // step1
        curr->next = prev->next->next; // step2
        prev->next->next = curr; // step3

        prev = curr;
        curr = curr->next;
    }
    head = dummy->next;
    delete dummy;
    return head;
}

19.删除链表的倒数第N个节点

双指针，fast先移动n步，然后fast和low同时走，fast到结尾，此时slow指向要删除节点的前一个 Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode f = head, s = head;
        for(int i = 0; i < n; i ++) f = f.next;
        if(f == null) return head.next;
        while(f.next != null)  {
            f = f.next; s = s.next;
        }
        s.next = s.next.next;
        return head;
    }
}

1
2
3
4
5
6
7
8
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* fast = head, *slow = head;
    for (int i = 0; i < n; i ++) fast = fast->next;
    if(!fast) return head->next;
    while(fast->next) fast = fast->next, slow = slow->next;
    slow->next = slow->next->next;
    return head; 
}

160.链表相交

很巧妙的方法: 一个从A走，一个从B走，谁先走到空，再绕到另一个开头走

  • 定会相交的起始节点碰面（即\(a + c + b = b + c + a\)）

example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode p = headA, q = headB;
    while(p != q) {
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
        }
        return p;
    }
}

1
2
3
4
5
6
7
8
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode*p = headA, *q = headB;
    while(p != q) {
        p = p ? p->next : headB; 
        q = q ? q->next : headA;
    }
    return p;
}

142.环形链表II

Q: 如何判断有环？ 判断出了如何找环的入口?

  • 快慢指针: 快的每次走两个，慢的走一个，若相遇则存在环
  • 找入口 → 动图参考, 太妙了!!
    • 头结点出发一个指针，相遇节点也出发一个指针，每次均只走一个节点，当两指针相遇即环形入口的节点 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode f = head, s = head;
        while(f != null && f.next != null) {
            f = f.next.next;
            s = s.next;
            if(s == f) {
                ListNode idx1 = f, idx2 = head;
                while(idx1 != idx2) {
                    idx1 = idx1.next;
                    idx2 = idx2.next;
                }
                return idx1;
            }
        }
        return null;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
ListNode *detectCycle(ListNode *head) {
    ListNode* fast = head, *slow = head;
    while(fast && fast->next) {
        slow = slow->next, fast = fast->next->next;
        if (slow == fast) {
            ListNode* idx1 = fast, *idx2 = head;
            while(idx1 != idx2) idx1 = idx1->next, idx2 = idx2->next;
            return idx1;
        }
    }
    return nullptr;
}

颜色主题调整

快来和我聊天~

可以的话请给我赞和 star喔~    =>  GitHub stars

评论