linkedlist
linkedlist
hexinyuan 发表于4个月前
linkedlist
  • 发表于 4个月前
  • 阅读 0
  • 收藏 0
  • 点赞 0
  • 评论 0
摘要: algorithm 刷题记录

1. dummy node

  • remove linked list elements
  • remove duplicates from sorted list
  • remove duplicates from sorted list ii (***)
  • swap two nodes in linked list
  • reverse linked list
  • reverse linked list ii (找到prem和postn,然后翻转指定的部分)
  • merge two sorted list
  • partition list (两个list,一个存放小的一个存放大的,然后将两个链表连起来,注意将大的末尾的next置为空) dummyNode.next = head 回收dummyNode:ret = dummyNode.next dummyNode = null

2. basic skills

  • insert a node in sorted list
  • remove a node from linked list
  • reverse linked list
  • find the middle of a linked list
  • merge two sorted list

3. fast&slow pointers

  • find the middle of linked list
  • linked list cycle (快慢指针,如果有环,快指针会追上慢指针,如果无环,快指针会走到空)
  • linked list cycle ii (相遇后,slow指针回到原点,然后slow和fast各走一步,会在入口处相遇)

4. demo

  • merge k sorted list
  • panlindrome linked list (***)
  • odd even linked list (***)
  • reorder list (1.快慢指针找中点 2.后半部分revers 3.合并两个链表) (与palindrome linked list类似)
  • rotate list
  • insertion sort list(链表插入排序)
  • sort list(1.快慢指针找中点 2.归并排序)
  • convert sorted list to bst
  • add two numbers
  • add two numbers ii
  • reverse nodes in k group
  • delete node in linked list(思路:把要删除节点的next的值赋给该节点,然后删除next,注意两个特殊情况node==null 和 node.next == null)
  • remove nth node from end of list(两根指针p,q,让q想走n+1步,然后pq同时走,当q走到null的时候,p刚好走到要删除节点的上一个位置,注意:非空判断)
  • copy list with random pointer (1.复制 2.复制random 3.断开返回复制出来的)

remove linked list elements


public class Solution {
    public ListNode removeElements(ListNode head, int val) {
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
            ListNode cur = head;//note:
            ListNode pre = dummyHead;
            while (cur != null) {
                if (cur.val == val) {
                    pre.next = cur.next;
                } else {
                    pre = pre.next;
                }
                cur = cur.next; 
            } 
            ListNode ret = dummyHead.next;
            dummyHead = null;
            return ret;
    }
}

remove a node from sorted list


public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode node = head;
        while (node.next != null) {
            if (node.val == node.next.val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
        return head;
    }
}

remove a node from sorted list ii (note)

>1->2->3->3->4->4->5, return 1->2->5. 1->1->1->2->3, return 2->3.



public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)
            return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;

        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int val = cur.next.val;
                while (cur.next != null && cur.next.val == val) {
                    cur.next = cur.next.next;
                }            
            } else {
                cur = cur.next;
            }
        }
        
        return dummy.next;
    }
}

swap two nodes in linked list


public class Solution { 
   public ListNode swapNodes(ListNode head, int v1, int v2) {
        // Write your code here
        ListNode dummy = new ListNode(-1);
        dummy.next = head; 
        ListNode cur = dummy; 
        ListNode p=null,q = null;

        while (cur != null && cur.next != null) {
            if (cur.next.val == v1) {
                p = cur;
            } else if (cur.next.val == v2) {
                q = cur;
            } 
            if (p != null &&  q != null) {
                break;
            } 
            cur = cur.next; 
        }


        if (p != null && q != null) { 
           if (p.next == q) {
               ListNode nextQ = q.next;
               p.next = nextQ;
               q.next = nextQ.next;
               nextQ.next = q;
           } else if (q.next == p) {
               ListNode nextP = p.next;
               q.next = nextP;
               p.next = nextP.next;
               nextP.next = p;
           } else {
               ListNode nextP = p.next;
               ListNode nextNextP = nextP.next;
               ListNode nextQ = q.next; 
               p.next = q.next;
               q.next = nextP;
               nextP.next = nextQ.next;
               nextQ.next = nextNextP; 
           }
        } 
       return dummy.next; 
    }
}

reverse linked list


public ListNode reverseList(ListNode head) {
   if (head == null) {
       return null;
   } 

   ListNode prev = null;
   ListNode cur = head; 

   while (cur != null) {
        ListNode temp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = temp;
   } 
   return prev;  
}
 

reverse linked list

hint:找到prem和postn,然后翻转

Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.


public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m >= n || head == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        
        for (int i = 1; i < m; i++) {
            if (head == null) {
                return null;
            }
            head = head.next;
        }
        
        ListNode premNode = head;
        ListNode mNode = head.next;
        ListNode nNode = mNode, postnNode = mNode.next;
        for (int i = m; i < n; i++) {
            if (postnNode == null) {
                return null;
            }
            ListNode temp = postnNode.next;
            postnNode.next = nNode;
            nNode = postnNode;
            postnNode = temp;
        }
        mNode.next = postnNode;
        premNode.next = nNode;
        
        return dummy.next;
    }
}

merge two sorted list


public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode lastNode = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                lastNode.next = l1;
                l1 = l1.next;
            } else {
                lastNode.next = l2;
                l2 = l2.next;
            }
            lastNode = lastNode.next;
        }
        
        if (l1 != null) {
            lastNode.next = l1;
        } else {
            lastNode.next = l2;
        }
        
        return dummy.next;
    }
}

partition list



public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        
        ListNode leftDummy = new ListNode(0);
        ListNode rightDummy = new ListNode(0);
        ListNode left = leftDummy, right = rightDummy;
        
        while (head != null) {
            if (head.val < x) {
                left.next = head;
                left = head;
            } else {
                right.next = head;
                right = head;
            }
            head = head.next;
        }
        
        right.next = null;
        left.next = rightDummy.next;
        return leftDummy.next;
    }
}

find the midddle

> 1 2 3 4 5 s f s f s f
1 2 3 4 5 6 s f s f s f


private ListNode findMiddle(ListNode head) {
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

linked list cycle


public class Solution {
    public Boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode fast, slow;
        fast = head.next;
        slow = head;
        while (fast != slow) {
            if(fast==null || fast.next==null)
                return false;
            fast = fast.next.next;
            slow = slow.next;
        } 
        return true;
    }
}

linked list cycle ii

>方法三(最简单):

第一次相遇时slow走过的距离:a+b,fast走过的距离:a+b+c+b。

因为fast的速度是slow的两倍,所以fast走的距离是slow的两倍,有 2(a+b) = a+b+c+b,可以得到a=c(这个结论很重要!)。

我们发现L=b+c=a+b,也就是说,从一开始到二者第一次相遇,循环的次数就等于环的长度。

  1. 我们已经得到了结论a=c,那么让两个指针分别从X和Z开始走,每次走一步,那么正好会在Y相遇!也就是环的第一个节点。

  2. 在上一个问题的最后,将c段中Y点之前的那个节点与Y的链接切断即可。

  3. 如何判断两个单链表是否有交点?先判断两个链表是否有环,如果一个有环一个没环,肯定不相交;如果两个都没有环,判断两个列表的尾部是否相等;如果两个都有环,判断一个链表上的Z点是否在另一个链表上。

如何找到第一个相交的节点?求出两个链表的长度L1,L2(如果有环,则将Y点当做尾节点来算),假设L1<L2,用两个指针分别从两个链表的头部开始走,长度为L2的链表先走(L2-L1)步,然后两个一起走,直到二者相遇。



public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next==null) {
            return null;
        }

        ListNode fast, slow;
        fast = head.next;
        slow = head;
        while (fast != slow) {
            if(fast==null || fast.next==null)
                return null;
            fast = fast.next.next;
            slow = slow.next;
        } 
        
        while (head != slow.next) {
            head = head.next;
            slow = slow.next;
        }
        return head;
    }
}

merge k sorted list

分治法


public class Solution {
    
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists.size() == 0) {
            return null;
        }
        return mergeHelper(lists, 0, lists.size() - 1);
    }
    
    private ListNode mergeHelper(List<ListNode> lists, int start, int end) {
        if (start == end) {
            return lists.get(start);
        }
        
        int mid = start + (end - start) / 2;
        ListNode left = mergeHelper(lists, start, mid);
        ListNode right = mergeHelper(lists, mid + 1, end);
        return mergeTwoLists(left, right);
    }
    
    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                tail = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                tail = list2;
                list2 = list2.next;
            }
        }
        if (list1 != null) {
            tail.next = list1;
        } else {
            tail.next = list2;
        }
        
        return dummy.next;
    }
}

heap


public class Solution {
    private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
        public int compare(ListNode left, ListNode right) {
            return left.val - right.val;
        }
    };
    
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        
        Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), ListNodeComparator);
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                heap.add(lists.get(i));
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode head = heap.poll();
            tail.next = head;
            tail = head;
            if (head.next != null) {
                heap.add(head.next);
            }
        }
        return dummy.next;
    }
}


panlindrome linked list



public class Solution { 
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        
        ListNode middle = findMiddle(head);
        middle.next = reverse(middle.next);
        
        ListNode p1 = head, p2 = middle.next;
        while (p1 != null && p2 != null && p1.val == p2.val) {
            p1 = p1.next;
            p2 = p2.next;
        }
        
        return p2 == null;
    }
    
    private ListNode findMiddle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
    
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        
        return prev;
    }
}

odd even linked list


public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        while(odd.next != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

reorder list


public class Solution {
   public void reorderList(ListNode head) {
            if (head == null || head.next == null) {
                return;
            }
            //1.找到中点
            ListNode middle = findMiddle(head);
            //2.反转后半部分
            middle.next = reverse(middle);
            //3.合并两个部分
            ListNode left = head;
            ListNode right = middle.next;
            head = merge(left, right, middle);
            System.out.println(head);
        }

         

        private ListNode findMiddle(ListNode node) {
            ListNode slow = node;
            ListNode fast = node.next;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }

        private ListNode reverse(ListNode pre) {
            ListNode cur = pre.next;
            ListNode curPost  = null;
            if (cur != null) { 
                curPost = cur.next; 
                while (cur != null && curPost != null) {
                    ListNode temp = curPost.next;
                    curPost.next  = cur;
                    cur = curPost;
                    curPost = temp;
                }
                pre.next.next = curPost;
                pre.next = cur; 
            }
            return pre.next; 
        } 
        
         
        private ListNode merge(ListNode left, ListNode right, ListNode middle) {
            ListNode dummy = new ListNode(0);
            ListNode tail = dummy;

            while (right != null) {
                tail.next = left;
                tail = tail.next;
                left  = left.next;

                tail.next = right;
                tail = tail.next;
                right = right.next;
            }

            if (left == middle) {
                tail.next = left;
                tail = tail.next;
            }
            tail.next = null;
            return dummy.next;
        } 
}
 

public void reorderList(ListNode head) {
    if(head==null||head.next==null) return;
    
    //Find the middle of the list
    ListNode p1=head;
    ListNode p2=head;
    while(p2.next!=null&&p2.next.next!=null){ 
        p1=p1.next;
        p2=p2.next.next;
    }
    
    //Reverse the half after middle  1->2->3->4->5->6 to 1->2->3->6->5->4
    ListNode preMiddle=p1;
    ListNode preCurrent=p1.next;
    while(preCurrent.next!=null){
        ListNode current=preCurrent.next;
        preCurrent.next=current.next;
        current.next=preMiddle.next;
        preMiddle.next=current;
    }
    
    //Start reorder one by one  1->2->3->6->5->4 to 1->6->2->5->3->4
    p1=head;
    p2=preMiddle.next;
    while(p1!=preMiddle){
        preMiddle.next=p2.next;
        p2.next=p1.next;
        p1.next=p2;
        p1=p2.next;
        p2=preMiddle.next;
    }
}

rotate list


public class Solution {
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length ++;
            head = head.next;
        }
        return length;
    }
    
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        
        int length = getLength(head);
        n = n % length;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        
        ListNode tail = dummy;
        for (int i = 0; i < n; i++) {
            head = head.next;
        }
        
        while (head.next != null) {
            tail = tail.next;
            head = head.next;
        }
        
        head.next = dummy.next;
        dummy.next = tail.next;
        tail.next = null;
        return dummy.next;
    }
}

insertion sort list (****)



public class Solution {
     public ListNode  insertionSortList(ListNode head) {  
        ListNode dummy = new ListNode(Integer.MIN_VALUE);  
        ListNode cur = head;  
        while (cur != null){  
            ListNode pos = findInsertPos(dummy, cur.val);  
            ListNode tmp = cur.next; //记录当前遍历节点的下一个节点,以便继续遍历下个节点  
            cur.next = pos.next;  
            pos.next = cur;  
            cur = tmp;  
        }  
        return dummy.next;  
    }  

    //找到当前遍历点cur的插入位置  
    private ListNode  findInsertPos(ListNode head, int x){  
        ListNode  pre = null;  
        ListNode  cur = head;  
        while (cur != null && cur.val <= x){  
            pre = cur;  
            cur = cur.next;  
        }  
        return pre;  
    } 
}

sort list

// version 1: Merge Sort
public class Solution {            
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }    

    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tail.next = head1;
                head1 = head1.next;
            } else {
                tail.next = head2;
                head2 = head2.next;
            }
            tail = tail.next;
        }
        if (head1 != null) {
            tail.next = head1;
        } else {
            tail.next = head2;
        }

        return dummy.next;
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode mid = findMiddle(head);

        ListNode right = sortList(mid.next);
        mid.next = null;
        ListNode left = sortList(head);

        return merge(left, right);
    }
}




// version 2: Quick Sort 1
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode mid = findMedian(head); // O(n)
        
        ListNode leftDummy = new ListNode(0), leftTail = leftDummy;
        ListNode rightDummy = new ListNode(0), rightTail = rightDummy;
        ListNode middleDummy = new ListNode(0), middleTail = middleDummy;
        while (head != null) {
            if (head.val < mid.val) {
                leftTail.next = head;
                leftTail = head;
            } else if (head.val > mid.val) {
                rightTail.next = head;
                rightTail = head;
            } else {
                middleTail.next = head;
                middleTail = head;
            }
            head = head.next;
        }
        
        leftTail.next = null;
        middleTail.next = null;
        rightTail.next = null;
        
        ListNode left = sortList(leftDummy.next);
        ListNode right = sortList(rightDummy.next);
        
        return concat(left, middleDummy.next, right);
    }
    
    private ListNode findMedian(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    private ListNode concat(ListNode left, ListNode middle, ListNode right) {
        ListNode dummy = new ListNode(0), tail = dummy;
        
        tail.next = left; tail = getTail(tail);
        tail.next = middle; tail = getTail(tail);
        tail.next = right; tail = getTail(tail);
        return dummy.next;
    }
    
    private ListNode getTail(ListNode head) {
        if (head == null) {
           return null;
        } 
       
        while (head.next != null) {
            head = head.next;
        }
        return head;
    }
}

convert sorted list to bst


public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {return null;}
        if (head.next == null) {return new TreeNode(head.val);}
        
        ListNode slow = head;
        ListNode fast = head;
        ListNode last = slow; 
        
        while (fast.next != null && fast.next.next != null) {
            last = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow.next;
        last.next = null;
        TreeNode cur = new TreeNode(slow.val);
        if (head != slow) cur.left = sortedListToBST(head);
        cur.right = sortedListToBST(fast);
        return cur;
    }
}

remove nth node from end of list


public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n <= 0) {
            return null;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode preDelete = dummy;
        for (int i = 0; i < n; i++) {
            if (head == null) {
                return null;
            }
            head = head.next;
        }
        while (head != null) {
            head = head.next;
            preDelete = preDelete.next;
        }
        preDelete.next = preDelete.next.next;
        return dummy.next;
    }
}

add two numbers


public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null) {
            return null;
        }
            
        ListNode head = new ListNode(0);
        ListNode point = head;
        int carry = 0;
        while(l1 != null && l2!=null){
            int sum = carry + l1.val + l2.val;
            point.next = new ListNode(sum % 10);
            carry = sum / 10;
            l1 = l1.next;
            l2 = l2.next;
            point = point.next;
        }
        
        while(l1 != null) {
            int sum =  carry + l1.val;
            point.next = new ListNode(sum % 10);
            carry = sum /10;
            l1 = l1.next;
            point = point.next;
        }
        
        while(l2 != null) {
            int sum =  carry + l2.val;
            point.next = new ListNode(sum % 10);
            carry = sum /10;
            l2 = l2.next;
            point = point.next;
        }
        
        if (carry != 0) {
            point.next = new ListNode(carry);
        }
        return head.next;
    }
}

add two numbers ii

version1 : stack



public class Solution {
   public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       //require
       ListNode ans=null;
       Stack<ListNode> stack1=new Stack<ListNode>(),stack2=new Stack<ListNode>();
       //invariant
       while(l1!=null||l2!=null){
           if(l1!=null){
               stack1.push(l1);
               l1=l1.next;
           }
           if(l2!=null){
               stack2.push(l2);
               l2=l2.next;
           }
       }
       int a=0,b=0,carry=0,sum=0;
       while(!stack1.isEmpty()||!stack2.isEmpty()){
           if(!stack1.isEmpty())
               a=stack1.pop().val;
           else
               a=0;
           if(!stack2.isEmpty())
               b=stack2.pop().val;
           else
               b=0;
           sum=a+b+carry;
           ListNode tmp=new ListNode(sum%10);
           tmp.next=ans;
           ans=tmp;
           carry=sum/10;
       }
       if(carry!=0){
           ListNode tmp=new ListNode(carry);
           tmp.next=ans;
           ans=tmp; 
       }

       //ensure
       return ans;
   }
}

version 2: reverse list 结合 add two numbers

reverse nodes in k group

1、建立空的新链表list1. 2、如果原链表剩余元素个数不小于K个,则取K个元素,采用头插法构建反序的临时链表,插入list1的尾部。 3、如果链表剩余元素个数小于K个,则将剩余的链表插入到list1的尾部。


private static ListNode reverse(ListNode pre, ListNode next){
    ListNode last = pre.next;//where first will be doomed "last"
    ListNode cur = last.next;
    while(cur != next){
        last.next = cur.next;
        cur.next = pre.next;
        pre.next = cur;
        cur = last.next;
    }
    return last;
}

public static ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || k == 1)
            return head;
            
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int count = 0;
        ListNode pre = dummy;
        ListNode cur = head;
        while(cur != null){
            count ++;
            ListNode next = cur.next;
            if(count == k){
                pre = reverse(pre, next);
                count = 0;   
            }
            cur = next;
        }
     return dummy.next;
}

swap nodes in pairs


public class Solution {
  
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        head = dummy;
        while (head.next != null && head.next.next != null) {
            ListNode n1 = head.next, n2 = head.next.next;
            // head->n1->n2->...
            // => head->n2->n1->...
            head.next = n2;
            n1.next = n2.next;
            n2.next = n1; 
            // move to next pair
            head = n1;
        } 
        return dummy.next;
    }
}
共有 人打赏支持
粉丝 0
博文 2
码字总数 9884
×
hexinyuan
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: