链表OJ题（上）

✅每日一练：876. 链表的中间结点 - 力扣（LeetCode）

---

 解题思路：

    定义快慢指针，让快指针走2步，慢指针走1步，当fast或者fast.next为空时，走完链表，此时slow就是中间位置

public ListNode middleNode(ListNode head) {//定义快慢指针，让快指针走2步，慢指针走1步，当fast或者fast.next为空时，走完链表，此时slow就是中间位置ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}

---

✅每日一练：203. 移除链表元素 - 力扣（LeetCode）

---

 

 解题思路：

   题目意思让我们删除链表中相同的元素，看图

 

public ListNode removeElements(ListNode head, int val) {//判断头结点是否为空if (head == null) {return null;}//定义两个指针ListNode prev = head;ListNode cur = head.next;//循环条件while (cur != null) {if (cur.val == val) {prev.next = cur.next;cur = cur.next;} else {prev = cur;cur = cur.next;}}//如果第一个元素就是我们要删除的节点，直接让head = head.nextif (head.val == val) {head = head.next;}return head;}

---

✅每日一练：206. 反转链表 - 力扣（LeetCode）

 

解题思路：

   题目意思很简单 ，就是逆序一个单链表，思路就是先把头结点置空，然后将后面的节点挨个进行头插，反转链表，逻辑看似简单，实现起来还是有很多细节的，常看，不然就会忘，如图

这里面还有细节，就是头结点为空时，说明没有节点，如果head.next = null,说明就一个节点，直接返回头结点就可：

public ListNode reverseList(ListNode head) {if (head == null) {return null;}if (head.next == null) {return head;}ListNode cur = head.next;//将头结点置空，将后面的节点逐一进行头插head.next = null;while (cur != null) {ListNode curNext = cur.next;cur.next = head;head = cur;cur = curNext;}return head;}

---

✅每日一练：链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

---

 

 解题思路：

   定义快慢指针，让快指针先走k-1步，走完以后让快慢指针同时走一步，当快fast.next为空时，说明走完了，此时slow就是我们要找的元素，非常巧妙，是谁想到的，真是太强了，我画个图吧

 

public ListNode FindKthToTail(ListNode head, int k) {if (k <= 0 || head == null) {return null;}//定义快慢指针，让快指针走2步，慢指针走k-1步，再让slow和fast同时走一步，让fast.next为空时，//表示走完了，此时的慢指针就是倒数第k个节点的数值ListNode fast = head;ListNode slow = head;//fast走k-1步while (k - 1 != 0) {fast = fast.next;//当k的值大于链表的长度时，用于判断下一个fast是否为空if (fast == null) {return null;}k--;}while (fast.next != null) {fast = fast.next;slow = slow.next;}return slow;}

---

✅每日一练：21. 合并两个有序链表 - 力扣（LeetCode）

---

 

 解题思路：

    这题有点像合并两个有序数组，定义一个临时的头结点，将两个链表的头结点的值进行比较，哪个小作为头结点，然后交叉比较两个链表，比较值的大小，小的房前面，形成有序，大致思路就是这样：

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newHead = new ListNode();ListNode tmp = newHead;while (list1 != null && list2 != null) {if (list1.val < list2.val) {tmp.next = list1;list1 = list1.next;tmp = tmp.next;} else {tmp.next = list2;list2 = list2.next;tmp = tmp.next;}}if (list1 != null) {tmp.next = list1;}if (list2 != null) {tmp.next = list2;}//返回新的头结点return newHead.next;}