链表-Leetcode

😃LeetCode 19. 删除链表的倒数第N个节点

//两次遍历法
class Solution {
    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;
        first = dummy;
        while (length > 0) {
            length--;
            first = first.next;
        }
        first.next = first.next.next;
        return dummy.next;
    }
}

😁LeetCode 24. 两两交换链表中的节点

class Solution {
    public ListNode swapPairs(ListNode head) {
        //头插法
        ListNode dumb = new ListNode(0);
        dumb.next = head;
        ListNode temp = dumb;
        while(temp.next!=null&&temp.next.next!=null){
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            temp.next = end;
            start.next = end.next;
            end.next = start;
            temp = start;
        }
        return dumb.next;   
    }
}

LeeCode 83. 删除排序链表中的重复元素

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        //这里不用哑结点
        ListNode cur = head;
        while(cur != null && cur.next != null){
            if(cur.next.val == cur.val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return head;   
    }
}

LeetCode 141. 环形链表

 //HashSet解法：add, remove,isEmpty,contains,clear,size
 /**
public class Solution {
    public boolean hasCycle(ListNode head) {
       HashSet<ListNode> hasExist = new HashSet<>();
       while(head != null){
           if(hasExist.contains(head)){
               return true;
           }else{
               hasExist.add(head);
               head = head.next;
           }
       }
        return false;
    }
}
 */
//双指针解法
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;
        }
        //快慢指针
        ListNode slow = head;
        ListNode fast = head.next;
        //循环终止条件：slow==fast
        while(slow!=fast){
            if(fast==null||fast.next==null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

LeetCode 203. 移除链表元素

//头插法
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //因为head.val可能等于val,所以需要new一个哑结点，并且指向头结点
        ListNode dumb = new ListNode(0);
        dumb.next = head;
        //用于遍历链表的指针
        ListNode cur = dumb;
        //循环条件cur.next!=null
        while(cur.next!=null){
            if(cur.next.val==val){
                cur.next = cur.next.next;   
            }else{//这里要用else,因为存在连续等于val的结点
                cur = cur.next;
            }
        }
        return dumb.next;     
    }
}

LeetCode 206. 反转链表

//迭代法
class Solution {
    public ListNode reverseList(ListNode head) {
        //头结点指向null
        ListNode prev = null;
        ListNode temp = head;
        while(temp!=null){
			ListNode nextTemp = temp.next;
            temp.next = prev;
            prev = temp;
            temp = nextTemp;
        }
        return prev;
    }
}

LeetCode 876. 链表的中间结点

class Solution {
    public ListNode middleNode(ListNode head) {
        //快慢指针
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null&&fast.next!=null){
            //慢指针走一步快指针走两步
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;  
    }
}

头插法，哑巴结点（dumb，dumb.next=head)，遍历指针（temp=head，或temp=dumb）(temp=temp.next），循环条件(temp!=null，temp.next!=null），快慢指针，删除结点（temp.next=temp.next.next）