LeetCode初级算法——链表

  在LeetCode初级算法的链表专题中，共给出了六道题目，分别为：删除链表中的节点、删除链表的倒数第N个节点、反转链表、合并两个有序链表、回文链表、环形链表。在链表问题中，主要需要注意的是“双指针解法”、“快慢指针”，另外带头节点的链表可以简化很多操作，依次记录如下。

删除链表中的节点 （237）

  题目描述: 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。链表至少包含两个节点。链表中所有节点的值都是唯一的。给定的节点为非末尾节点并且一定是链表中的一个有效节点。不要从你的函数中返回任何结果。
  例如: 输入: head = [4,5,1,9], node = 5    输出: [4,1,9]
  解析: 本题的关键在于只给出了要删除的节点，而没有给出链表的其他任何节点，无法对链表进行遍历。一种比较巧妙的方法是：将要删除节点的后一个节点的值赋给它，然后删除其后一个节点，进行一个转化处理。

	public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

删除链表的倒数第N个节点 （19）

  题目描述: 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
  例如: 给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.
  解析:有两种方法可以实现这个问题：（1）两趟扫描。第一趟扫描得到链表的长度L，然后第二次扫描即知道要删除的是第L-n+1个节点，我们把第(L−n)个结点的next指针重新链接至第(L−n+2)个结点，完成这个算法。
  (2) 利用快慢指针实现一次扫描。可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n+1步，而第二个指针将从列表的开头出发。现在，这两个指针被n个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第n个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点即可。

	//方法一：两次扫描
	public ListNode removeNthFromEnd(ListNode head, int n) {
    	ListNode dummy = new ListNode(0);
    	dummy.next = head;  //加头节点
    	int length  = 0;
    	ListNode first = head;
    	while (first != null) {  //第一次扫描，得到链表长度
        	length++;
            first = first.next;
        }
    	length -= n;  //第L-n个
    	first = dummy;
        while (length > 0) {
        	length--;
        	first = first.next;
    	}
    	first.next = first.next.next;
    	return dummy.next;
	}
    
    //方法二：一次扫描，快慢指针
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next=head; //加头节点
        ListNode first=dummy,second=dummy;
        for(int i=0;i<n+1;i++)  //第一个指针先走n+1步
            first=first.next;
        while(first!=null){ //保持n的间隔向前
            first=first.next;
            second=second.next;
        }
        second.next=second.next.next; //删掉second.next
        return dummy.next;
    }

反转链表 （206）

  题目描述: 反转一个单链表。
  例如: 输入: 1->2->3->4->5->NULL   输出: 5->4->3->2->1->NULL
  解析: 可以迭代或递归地反转链表。（1）三指针法。从头开始遍历，每次将一个指向反转。在草稿纸上画出草图，很明显需要三个临时指针。反转后所有指针向后移动一步。知道最后一个指针指向空。最后更新一下最后一个节点的指向。（2）递归法。在递归函数里要做的就是三件事：第一，记录即将被递归调用节点的前驱（或者换句话说，建立个新的节点指向输入的下一个节点，之后递归调用那个新节点）；第二，递归调用输入的下一个节点；第三，将返回结果的末尾指向记录好的前驱节点，完成反转。

	//方法一：三指针法
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode begin = head;
        ListNode cur = null;
        while(begin.next!=null){
            ListNode temp=begin.next;
            begin.next=cur;
            cur = begin;
            begin = temp;
        }
        begin.next = cur;
        return begin;
    }
    //方法二：递归法
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head; //处理最小输入的情况，即空链表和单节点链表
        ListNode second = head.next; //将即将被调用的下一个节点分离，即将下一个调用的输入存在second里
        ListNode reverseHead = reverseList(second); //将调用后的结果存储
        second.next = head; //上面一步的调用已经完成以second为首的链表的反转，所以现在second变成了反转完成后的尾节点，把这个尾节点的next指向一开始输入的前驱，即head，完成整个链表反转
        head.next = null; //最开始的头节点要变成尾节点，即在后面补null使链表终结
        return reverseHead; 
    }

合并两个有序链表 （21）

  题目描述:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
  例如: 输入：1->2->4, 1->3->4    输出：1->1->2->3->4->4
  解析: 此题比较简单，类似于归并排序。

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(-1); //定义一个新的链表，此为头结点
        ListNode res = result;
        while(l1!=null && l2!=null){  //遍历两个链表，进行归并
            if(l1.val <= l2.val){ //小的先链接
                result.next = l1;
                l1=l1.next;
            }else{
                result.next = l2;
                l2=l2.next;
            }
            result=result.next;
        }
        if(l1==null) //l1遍历完，直接将剩余的l2链接过来
            result.next = l2;
        else if(l2==null) //l2遍历完，直接将剩余的l1链接过来
            result.next  = l1;
        return res.next;
    }

回文链表 （234）

  题目描述:请判断一个链表是否为回文链表。
  例如: 输入: 1->2   输出: false    输入: 1->2->2->1   输出: true
  解析: 将一半链表反转，与另一半进行比较。先设两个指针，通过快慢指针遍历链表，找到单链表的中间结点（可以采取快慢指针的方法，快指针每次循环前进两步，慢指针每次循环前进一步，当快指针到达链表的结尾时，慢指针指向的结点恰好是链表的中间结点），然后将链表的后半段进行反转，前后两段进行比较，则可判断是否为回文链表。

    public boolean isPalindrome(ListNode head) {
        ListNode fast=head,slow=head; //快慢指针
        while(fast!=null){ //快慢指针的遍历，slow处于中间位置（考虑奇偶）
            slow = slow.next;
            fast = fast.next!=null ? fast.next.next : fast.next;
        }
        //将链表后半段反转
        ListNode lastReverse=slow; //链表后半段的反转
        ListNode pre=null,last=null;
        while(lastReverse!=null){
            last = lastReverse.next;
            lastReverse.next = pre;
            pre = lastReverse;
            lastReverse = last;
        }
        //两段进行比较
        while(pre!=null && head != null){
            if(head.val != pre.val)
                return false;
            head = head.next;
            pre = pre.next;
        }
        return true;
    }

环形链表 （141）

  题目描述: 给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
  例如: 输入：head = [3,2,0,-4], pos = 1   输出：true
  解析: 判断链表是否有环，可以使用快慢指针法，快指针一次走两步，慢指针一次走一步，若有环，经过多次遍历后，两指针必定再次相遇。

    public boolean hasCycle(ListNode head) {
        ListNode fast = head; //快慢指针
        ListNode slow = head;
        while(fast!=null){
            if(fast.next==null) break;
            slow = slow.next; //慢指针一次走一步，快指针一次两步，若有环，必相遇
            fast = fast.next.next;
            if(slow == fast)
                return true;
        }
        return false;
    }

总结

  本博客记录了LeetCode初级算法中链表模块给出的六道题目，相对比较简单，主要是对链表插入、删除、遍历等基本操作的使用，同时一个实用的技巧是快慢指针法。