链表的OJ题练习

1、给你单链表的头节点

head

，请你反转链表，并返回反转后的链表。

✈✈【OJ链接】反转链表

😵😵【思路】：总体逻辑改变链表地址的指向

**①设置prev代表前一个节点 **

②设置cur代替头节点进行遍历

③设置next来保存cur指向的下一个节点

核心代码为 next=cur.next; cur.next=prev; prev=cur; cur=next;

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

2、给你一个链表的头节点

head

和一个整数

val

，请你删除链表中所有满足

Node.val == val

的节点，并返回 新的头节点。

✈✈【OJ链接】移除链表元素

😵😵【思路】：总体逻辑把要删除节点的上一个节点指向的地址更改为要删除节点的下一个节点地址

①设置新节点prev=null放在头结点的前面充当上一个节点

②设置cur=head代表头节点进行遍历并判断cur.val与要删除的val是否相等

③、①cur.val==val的情况下设置新变量next=cur.next实现保存要删除节点cur的下一个节点 cur=next实现cur指的是要删除节点的下一个节点，然后prev.next=cur实现总体逻辑上说 的把要删除节点的上一个节点指向的地址更改为要删除节点的下一个节点地址

** ②cur.val!=val的情况下prev=cur; cur= cur.next;让prev和cur继续遍历**

特别注意：空链表情况、头节点也要删除的情况、和链表里元素全部都要删除的情况

    public ListNode removeElements(ListNode head, int val) {
          if (head==null)  return null;//空链表
            ListNode prev = null;
            ListNode cur = head;
            while (cur != null) {
                if (cur.val==val){
                    ListNode next=cur.next;
                    cur = next;
                    if (prev!=null) {
                        prev.next = cur;
                    }
                    
                    if (cur!=null){
                        next=cur.next;
                    }
                }
                else{
                    prev=cur;
                    cur=cur.next;
                }

            }
            if (prev==null) return null;//每一个节点都需要删除
            
            while (head!=null&&head.val==val){//头节点就是要删除的节点
                head=head.next;
            }
            return head;

    }

3、给定一个头结点为

head

的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

✈✈【OJ链接】链表的中间节点

**😵😵【思路】：总体逻辑利用快慢指针，快指针fast走两步慢指针slow走一步， 所以fast走到结 **

** 尾时slow刚好指向链表的中间节点**

    public ListNode middleNode(ListNode head) {
        
            if (head==null) return null;
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){//因为fast每次走两步所以要加上fast.next也不为空
                    fast=fast.next.next;
                    slow=slow.next;
                
            }
                return slow;

    }

完成啦~~~ ~~~