单链表面试题---移除链表元素和翻转链表

1.移除链表元素

题目链接：203. 移除链表元素 - 力扣（LeetCode）

解法一：定义两个指针

分别定义两个指针，分别为cur和prev，让cur=head.next，让prev=head。

如下图

cur指针是用来确定该节点的数据是否为要删除的数据，如果cur指向的节点的数据为要删除的数据，则我们让prev.next=cur.next，然后再让cur=cur.next。如果cur指向的节点中的数据不是要删除的，则让prev=cur，cur=cur.next。

过程图

假设11是我们要删除的数据，则观察图，看到cur指向的数据为11，则执行prev.next=cur.next，cur=cur.next

然后发现cur指向的节点中的数据不是要删除的数据，我们同时让prev=cur，cur=cur.next。

持续上面的步骤，一直到cur指向空。

但是以上这种写法，没有解决要删除的节点在头节点的问题，所以我们要将这一情况单独拿出来解决。

public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return head;
        }
        ListNode cur=head.next;
        ListNode prev=head;
        while(cur!=null){
            if(cur.val==val){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        //解决头节点为删除节点的情况
        if(head.val==val){
            head=head.next;
        }
        return head;
    }

解法二：定义一个新链表

我们可以定义一个新链表，然后将不是要删除的节点放到新节点，最后放回newHead.next。 

 

代码实现

public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return null;
        }
        ListNode newHead=new ListNode();
        ListNode cur=head;
        ListNode cur2=newHead;
        while(cur!=null){
            if(cur.val!=val){
                cur2.next=cur;
                //注意让cur2=cur
                cur2=cur;
            }
            cur=cur.next;
        } 
        cur2.next=null;
        return newHead.next;
    }

2. 翻转链表

翻转一个链表，我们可以定义一个cur=head.next，接着让cur指向的节点进行头插。

 代码实现

public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode cur=head.next;
        //要先将head.next变为空，因为后面head会变
        head.next=null;
        while(cur!=null){
            //记录cur的下一个节点，因为cur.next后面会变
            ListNode curN=cur.next;
            cur.next=head;
            head=cur;
            cur=curN;
        }
        return head;
    }