单链表面试题---移除链表元素和翻转链表_数据分析

1.移除链表元素

解法一：定义两个指针

分别定义两个指针，分别为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;
    }