算法面试3---链表

class Solution {

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            //1 每次修改前先把head.next备份否则head修改后找不到head.next
            ListNode nextTemp = head.next; 
            //2 修改head.next temp用来保存的是上次头节点的信息
            head.next = prev;
            //3 temp进行更新保存此次头节点的信息
            prev = head;
            //4 继续进行遍历
            head = nextTemp;
        }    
        //返回新链表的头结点
        return prev;        
    }
        
}

//递归版本的实现
class Solution {
    
    public ListNode reverseList(ListNode head) {
        //递归的终止条件
        if (head == null || head.next == null) return head;
        //递归处理的操作是从最后一个元素开始的
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

class Solution {

    public ListNode removeElements(ListNode head, int val) {
        //1 先处理头部要删除的元素。对于头结点要特殊处理，有可能传入的是空链表因此要判断一下，也有可能下一个头结点仍然为空因此需要进行while循环
        while(head != null && head.val == val){
            ListNode delNode = head;
            head = head.next;
            delNode.next = null;
        }
        //2 处理中间要删除的元素，有可能在上一步操作中已经把链表删除完了，因此在这一步应该判断一下链表是否为空了
        if (head == null) {
            return head;
        }
        //此时head肯定不是要删除的节点了
        ListNode prev = head;
        //找到要删除节点的前一个节点,这也正是前面为什么要头结点特殊处理一下的原因，头结点前面无节点了
        while (prev.next != null) {
            if (prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }else {
                //用prev进行遍历链表
                prev = prev.next;
            }
        }
        //返回删除后的链表
        return head;
    }
}

class Solution {

    public ListNode removeElements(ListNode head, int val) {
        // 定义一个虚拟的头结点，其值为多少并不重要
        ListNode dummyHead = new ListNode(0);
        // 让定义的虚拟头结点在链表的首部
        dummyHead.next = head;

        ListNode prev = dummyHead;
        //找到要删除节点的前一个节点,首元素的前面是虚拟头结点
        while (prev.next != null) {
            if (prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }else {
                //用prev进行遍历链表
                prev = prev.next;
            }
        }
        //返回删除后的链表
        return dummyHead.next;
    }
}

class Solution {

    public ListNode swapPairs(ListNode head) {
        // 先设置好虚拟头结点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        // 当结点不为空时才进行交换
        while (prev.next != null && prev.next.next != null){
            // node1根据prev定位,
            ListNode node1 = prev.next;
            ListNode node2 = node1.next;
            ListNode next = node2.next;
            // 进行交换
            node2.next = node1;
            node1.next = next;
            prev.next = node2;
            //移动prev
            prev = node1;
        }
        return dummyHead.next;
    }
}