0706学习

agile Posted on Jul 6 2023

面试 leetcode学习

-   剑指 Offer 18. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
题目保证链表中节点的值互不相同

---

```C#
public ListNode DeleteNode(ListNode head, int val)
{
    if (head.val == val)
    {
        head = head.next;
        return head;
    }

var pre = head;
    var current = head.next;
    while (current != null)
    {
        if (current.val == val)
        {
            pre.next = current.next;
            break;
        }

pre = current;
        current = current.next;
    }

return head;
}
```

-   剑指 Offer 22. 链表中倒数第 k 个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
![WX20230706-1144132x.png](https://tools.nxcloud.club:12500/images/2023/07/06/WX20230706-1144132x.png)

---
```C#
private int __index = 0;

public ListNode GetKthFromEnd(ListNode head, int k)
{
    if (head == null)
    {
        return head;
    }

var temp = GetKthFromEnd(head.next, k);
    __index++;
    if (k == __index)
    {
        temp = head;
    }

return temp;
}

public ListNode GetKthFromEnd2(ListNode head, int k)
{
    var first = head;
    var second = head;
    for (int i = 0; i < k; i++)
    {
        second = second.next;
    }

while (second != null && second.next != null)
    {
        second = second.next;
        first = first.next;
    }

return second != null ? first.next : first;
}
```

---

-   剑指 Offer 25. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

---

```C#
public ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
    if (l1 == null)
    {
        return l2;
    }

if (l2 == null)
    {
        return l1;
    }

var cl1 = l1;
    var cl2 = l2;
    ListNode head = null;
    if (cl1.val < cl2.val)
    {
        head = cl1;
        cl1 = cl1.next;
    }
    else
    {
        head = cl2;
        cl2 = cl2.next;
    }

var dfs = head;
    while (cl1 != null && cl2 != null)
    {
        if (cl1.val < cl2.val)
        {
            dfs.next = cl1;
            cl1 = cl1.next;
        }
        else
        {
            dfs.next = cl2;
            cl2 = cl2.next;
        }

dfs = dfs.next;
    }

dfs.next = cl1 != null ? cl1 : cl2;

return head;
}

//通过创建虚拟点实现
public ListNode MergeTwoLists2(ListNode l1, ListNode l2)
{
    var dummy = new ListNode(0);
    var current = dummy;
    while (l1 != null && l2 != null)
    {
        if (l1.val < l2.val)
        {
            current.next = l1;
            l1 = l1.next;
        }
        else
        {
            current.next = l2;
            l2 = l2.next;
        }

current = current.next;
    }

current.next = l1 != null ? l1 : l2;
    return dummy.next;
}

public ListNode MergeTwoLists3(ListNode l1, ListNode l2)
{
    if (l1 == null)
    {
        return l2;
    }

if (l2 == null)
    {
        return l1;
    }

ListNode l = null;
    if (l1.val < l2.val)
    {
        l = l1;
        l1.next = MergeTwoLists3(l1.next, l2);
    }
    else
    {
        l = l2;
        l2.next = MergeTwoLists3(l1, l2.next);
    }

return l;
}
```

---

-   剑指 Offer 52. 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。

![WX20230706-1615122x.png](https://tools.nxcloud.club:12500/images/2023/07/06/WX20230706-1615122x.png)
---
我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。 为此，我们必须消除两个链表的长度差
指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
如果 pA 到了末尾，则 pA = headB 继续遍历
如果 pB 到了末尾，则 pB = headA 继续遍历
比较长的链表指针指向较短链表head时，长度差就消除了
如此，只需要将最短链表遍历两次即可找到位置

---

![5a93835d37a739b389eb4819ff9f3e8f.png](https://tools.nxcloud.club:12500/images/2023/07/06/5a93835d37a739b389eb4819ff9f3e8f.png)

---

```C#
public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
{
    var currentA = headA;
    var currentB = headB;

// while (!(currentA == currentB || currentA == null && currentB == null))
    // {
    //     currentA = currentA.next != null ? currentA.next : headB;
    //     currentB = currentB.next != null ? currentB.next : headA;
    // }

while (currentA != currentB)
    {
        currentA = currentA != null ? currentA.next : headB;
        currentB = currentB != null ? currentB.next : headA;
    }

return currentA;
}
```

-   剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

---

```C#
public int[] Exchange(int[] nums)
{
    if (nums.Length == 0)
    {
        return nums;
    }

var p1 = 0;
    var p2 = nums.Length - 1;
    while (p1 < p2)
    {
        while (p1 < p2 && (nums[p1] & 1) == 1)
        {
            p1++;
        }

while (p1 < p2 && (nums[p2] & 1) != 1)
        {
            p2--;
        }

(nums[p1], nums[p2]) = (nums[p2], nums[p1]);
    }

return nums;
}
```

---

-   剑指 Offer 57. 和为 s 的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

---
![WX20230706-1703152x.png](https://tools.nxcloud.club:12500/images/2023/07/06/WX20230706-1703152x.png)

---
```C#
public int[] TwoSum(int[] nums, int target)
{
    if (nums.Length < 2)
    {
        return new[] { 0, 0 };
    }

var p1 = 0;
    var p2 = nums.Length - 1;
    while (p1 < p2)
    {
        if (target - nums[p2] == nums[p1])
        {
            return new[] { nums[p1], nums[p2] };
        }

if (target - nums[p2] > nums[p1])
        {
            p1++;
        }
        else
        {
            p2--;
        }
    }

return new[] { 0, 0 };
}
```

---