链表的基本操作

定义

class Node{
  Item item;//表示任意的数据类型
  Node next;//指向下一个节点的引用
}

从链表头部插入元素

Node oldFirst = first;//oldFirst指向原来的头结点
first = new Node();
first.item = item;
first.next = oldFirst;

从链表头部删除元素

first = first.next; //first指向first.next即可

从链表尾部插入元素

Node oldLast = last;
last = new Node();
last.item = item;
oldLast.next = last;

从中间插入和删除结点

Node first = new Node();
Node third = new Node();
first.next = third;
//在first和second之间插入second
Node second = new Node();
first.next = second;
second.next = third;
//删除second结点(删除结点必须知道前一个结点)
first.next = third;

栈和对列的实现

栈的实现

使用数组实现栈

public class ArrayStack<Item> implements Iterable<Item>{

    //初始化数组的大小
    private Item[] arr = (Item[])new Object[5];
    private int N == 0;
    
    public int size(){
        return N;
    }
    
    public boolean isEmpty(){
        return N == 0 ? true : false; 
    }
    
    public void push(Item item){
        if(N == arr.length){
            resize(2*N);
        }
        arr[N++] = item;
    }
    
    public Item pop(){
        Item item = arr[--N];
        arr[N] = null;
        if(N > 0 && N == arr.length/4){
            resize(2*N);
        }
        return item;
    }
    //动态调整数组大小
    public void resize(int capacity){
        Item[] temp = (Item[])new Object[capacity];
        for(int i = 0; i < N; i++){
           temp[i] = arr[i];
        }
        arr = temp;
    }
    
    //实现迭代器功能，可以使用foreach语句
    public Iterator<Item> iterator(){
        return new ArrayReverseIterator();
    }
    
    private class ArrayReverseIterator implements Iterator<Item>{
        private int index = N;
        public boolean hasNext(){
            return N > 0 ? true : false;
        }
        
        public Item next(){
            return arr[--N];
        }
    }
}

使用链表实现栈

public class NodeStack<Item> implements Iterable<Item> {

    private class Node{
        Item item;
        Node next;
    }

    private Node first;
    private int N = 0;

    public void push(Item item){
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }

    public Item pop(){
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }

    public boolean isEmpty(){
        return N == 0;
    }

    public int size(){
        return N;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ListIterator();
    }


    private class ListIterator implements Iterator<Item>{

        private Node current = first;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

}

队列的实现

public class Queue<Item> implements Iterable<Item>{
    
    private class Node{
        Item item;
        Node next;
    }
    
    Node first;
    Node last;
    private int N = 0;
    
    public boolean isEmpty(){
        return N == 0;
    }
    
    public int size(){
        return N;
    }
    
    public void enqueue(Item item){
        Node oldLast = last;
        last = new Node();
        last.item = item;
        if(isEmpty()){
            first = last;
        }else{
            oldLast.next = last;
        }
        N++;
    }
    
    public Item dequeue(){
        Item item = first.item;
        first = first.next;
        if(isEmpty()){
            last = null;
        }
        N--;
        return item;
    }
    
    public Iterator<Item> iterator(){
       return new QueueIterator();
    }
    
    private class QueueIterator implements Iterator<Item>{
        
        private Node current = first;
        
        public boolean hasNext(){
            return current != null;
        }
        
        public Item next(){
            Item item = current.item;
            current = current.next;
            return item;
        }
        
    }
    
}

链表练习题目

1.有一个整数val，如何在节点值有序的环形链表中插入一个节点值为val的节点，并且保证这个环形单链表依然有序.给定链表的信息，及元素的值A及对应的nxt指向的元素编号同时给定val，请构造出这个环形链表，并插入该值。

class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
      this.val = val;
    }
}
public ListNode insert(int[] A, int[] next, int val){
    
    if(A == null || A.length == 0){
        ListNode node = new ListNode(val);
        return node;
    }
    ListNode head = new ListNode(A[0]);
    ListNode point = head;
    ListNode current = null;
    //通过数组构造链表
    for(int i = 0; i < next.length - 1; i++){
        current = new ListNode(A[next[i]]);
        ponit.next = current;
        point = current;
    }
    
    
    if(val < head.val){
        ListNode node = new ListNode(val);
        node.next = head;
        head = node;
        return head;
    }
    
    if(val > current.val){
       ListNode node = new ListNode(val);
       current.next = node;
       return head;
    }
    
    ListNode p1 = head;
    ListNode p2 = head.next;
    while(p1 != null && p2 != null){
        if(p1.val <= val && val <= p2.val){
            ListNode node = new ListNode(val);
            p1.next = node;
            node.next = p2;
            return head;
        }else{
            p1 = p1.next;
            p2 = p2.next;
        }
    }
    
    return head;
    
    
}

2.实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。给定带删除的节点，请执行删除操作，若该节点为尾节点，返回false，否则返回true.

public boolean remove(ListNode pNode){
        if(pNode.next == null){
            return false;
        }
        pNode.val = pNode.next.val;
        pNode.next = pNode.next.next;
        return true;
}

3.对于一个链表，我们需要用一个特定阈值完成对它的分化，使得小于等于这个值的结点移到前面，大于该值的结点在后面，同时保证两类结点内部的位置关系不变。给定一个链表的头结点head，同时给定阈值val，请返回一个链表，使小于等于它的结点在前，大于等于它的在后，保证结点值不重复。

public ListNode listDivide(ListNode head,int val){

    public ListNode head_1 = null;
    public ListNode tail_1 = null;
    public ListNode head_2 = null;
    public ListNode tail_2 = null;
    public ListNode next = null;
    
    while(head != null){
       next = head.next;
       head.next = null;
       if(head.val <= val){
          ListNode oldTail_1 = tail_1;
          tail_1 = head;
          if(head_1 == null){
            head_1 = tail_1;
          }else{
            oldtail_1.next = tail_1;
          }
       }else if(head.val > val){
          ListNode oldTail_2 = tail_2;
          tail_2 = head;
          if(head_2 == null){
             head_2 = tail_2;
          }else{
             oldTail_2.next = tail_2;
          }
       }
       head = next;
    }
    
    if(tail_1 != null){
      tail_1.next = head_2;
    }
    
    return head_1 != null ? head_1 : head_2; 
    
}

4.有一个单链表，请设计一个算法，使得每K个节点之间逆序，如果最后不够K个节点一组，则不调整最后几个节点。例如链表1->2->3->4->5->6->7->8->null，K=3这个例子。调整后为，3->2->1->6->5->4->7->8->null。因为K==3，所以每三个节点之间逆序，但其中的7，8不调整，因为只有两个节点不够一组。

public ListNode inverse(ListNode head,int k){
    if(head == null || head.next == null || k < 2){
        return head;
    }
    ListNode pre = null;
    ListNode current = head;
    ListNode start = null;
    ListNode next = null;
    int count = 1;
    while(current != null){
        next = current.next;
        if(count == 3){
            start = pre == null ? head : pre.next;
            head = pre == null ? current : head;
            reverse(pre,start,current,next);
            pre = start;
            count = 0;
        }
        count++;
        current = next;
    }
    return head;
    
}

//先逆序k个节点
public void reverse(ListNode left,ListNode start,ListNode end,ListNode right){
    ListNode current = start.next;
    ListNode point = start;
    ListNode next = null;
    while(current != right){
        next = current.next;
        current.next = point;
        point = current;
        current = next;
    }
    if(left != null){
        left.next = end;
    }
    start.next = right;
}

5.如何判断一个单链表是否有环？有环的话返回进入环的第一个节点的值，无环的话返回-1。

 public int chkLoop(ListNode head, int adjust) {
        if(head == null){
            return -1;
        }
        boolean isCircle = false;
        ListNode fast = head;
        ListNode slow = head;
        while(slow != null && fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                isCircle = true;
                break;
            }
        }
        if(!isCircle){
            return -1;
        }
        fast = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow.val;

    }

6.现在有两个无环单链表，若两个链表的长度分别为m和n，请设计一个时间复杂度为O(n + m)， 额外空间复杂度为O(1)的算法，判断这两个链表是否相交。

public boolean chkIntersect(ListNode headA, ListNode headB) {

        if(headA == null || headB == null){
            return false;
        }
        boolean isIntersect = false;
        int lenA = 0;
        ListNode p1 = headA;
        while(p1 != null){
            p1 = p1.next;
            lenA++;
        }
        int lenB = 0;
        ListNode p2 = headB;
        while(p2 != null){
            p2 = p2.next;
            lenB++;
        }
        if(lenA >= lenB){
            isIntersect = isCrossing(headA,headB,lenA - lenB);
        }else{
            isIntersect = isCrossing(headB,headA,lenB - lenA);
        }
        return isIntersect;
    }

public boolean isCrossing(ListNode headA, ListNode headB, int num){
        ListNode curA = headA;
        boolean isCross = false;
        while(num != 0){
            curA = curA.next;
            num--;
        }
        ListNode curB = headB;
        while(curA != null && curB != null){
            if(curA == curB){
                isCross = true;
                break;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return isCross;
    }

7.如何判断两个有环单链表是否相交？相交的话返回第一个相交的节点，不想交的话返回空。

public boolean chkInter(ListNode head1, ListNode head2, int adjust0, int adjust1) {

        if(head1 == null || head2 == null){
            return false;
        }

        ListNode p1 = insert(head1);
        ListNode p2 = insert(head2);
        //入环节点相交
        if(p1 == p2){
            return true;
        }
        //环中相交
        ListNode start1 = p1.next;
        while(start1 != p1){
            if(start1 == p2){
                return true;
            }
            start1 = start1.next;
        }
        return false;
    }

    //入环节点
    public ListNode insert(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(slow != null && fast != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }
        fast = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }