链表 经典面试题 OJ

1. 删除链表中等于给定值 val 的所有节点。OJ链接

个人 解题思路：1.要删除这个节点就需要知道这个节点的前一个节点

                          2.把要删除节点的next值赋值给前一个节点的next

                          3.循环遍历链表判断

特殊情况：1.当head为null时，直接返回null即可。

                  2.遍历完成后需要再单独判断第一个节点是否是要删除的节点

代码如下：

 public ListNode removeElements(ListNode head, int val) {
       if(head == null)return null;
       //定义前一个节点
       ListNode pre = head;
       //要删除的节点
       ListNode cur = head.next;
       while(cur != null){         //这里注意 是从第二个节点开始判断的
            if(cur.val == val){
                pre.next = cur.next;
                cur = cur.next;
            }else{
                pre = pre.next;
                cur = cur.next;
            }
       }
       //这里需要再判断第一个元素是否是要删除的
       if(head.val == val){
           head = head.next;
       }
       return head;
    }

2.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。OJ链接

 个人解题思路：1. 定义两个指针，同时从链表头开始“走”。

                          2.快指针每次走两步，慢指针每次走一步。

                          3.当快指针走到链表最后一个节点时，满指针所在节点即为所求中间节点。

特殊情况：当链表节点为偶数个时，快指针会走到链表最后一个节点之后的null。

代码如下：

 public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){  //需要注意节点个数为偶数的情况 
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

3.判断链表是否回文 OJ链接

 个人解题思路：1.先找到链表的中间节点（方法同上）。

                          2.从中间节点开始翻转之后的链表。

                          3.定义两个指针分别从链表两边同时“走”，并判断val值是否相等。

注意： 两个指针同时走时循环的判断条件（当节点为偶数或者奇数个时）！

代码如下：

 public boolean chkPalindrome(ListNode head) {
       if(head == null){
           return false;
       }
        //1.先寻找链表的中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.从slow开始翻转之后的链表
        ListNode cur = slow.next;
        while(cur!=null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3.从链表两端同时走 
            //注意循环的判断条件  
        while(head!=slow&&head.next!=slow){
            if(head.val != slow.val){
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        //这里head==slow 或者head.next==slow 使循环结束  分别判断
        if(head.next==slow){
            if(head.val == slow.val){
                return true;
            }else{
                return false;
            }
        }
        return true;
 }

希望大家可以指出其中的不足，分享自己更好的想法！