1.单向链表数据结构

public class ListNode {
    int val; //节点
    ListNode next; //指向下一个节点
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { 
	this.val = val; 
	this.next = next; 
    }

    @Override
    public String toString() {
        String s = "";
        ListNode node = this;
        while (node!=null){
            s = s.concat(node.val + "->");
            node = node.next;
        }
        return s;
    }
}

2.链表的基础操作

2.1 建立链表

时间复杂度O(n)

public ListNode buildListNode(int[] arr){
        ListNode head = null;
        ListNode cur= null;
        for (int i = 0; i < arr.length; i++) {
            ListNode node = new ListNode(arr[i]);
            node.next = null;
            if(head == null){
                //1.头节点赋值
                head = node;
            }else{
                //2.遍历指针连接到新节点
                cur.next = node;
            }
            //3.遍历指针指向最新的节点
            cur = node;
        }
        return head;
    }

2.2 求链表的长度

时间复杂度O(n)

 public int length(ListNode head){
        int length = 0;
        if(head == null){
            return length;
        }
        //遍历链表即可
        ListNode cur = head;
        while(cur!=null){
            length++;
            cur = cur.next;
        }
        return length;
    }

2.3 在链表头部插入节点

时间复杂度O(1)

public ListNode insertHeadNode(ListNode head, int item){
        ListNode node;
        if(head == null){
            node = new ListNode(item);
        }else {
            node = new ListNode(item);
            node.next = head;
        }
        return node;
    }

2.4 在链表尾部插入节点

时间复杂度O(n)

 public ListNode insertTailNode(ListNode head, int item){
        ListNode node;
        if(head == null){
            node = new ListNode(item);
            head = node;
        }else {
            //找到链表的尾部
            ListNode cur = head;
            while(cur.next!=null){
                cur = cur.next;
            }
            //插入节点
            node = new ListNode(item);
            cur.next = node;
        }
        return head;
    }

2.5 在有序链表中插入节点并保持有序

思路：在查找过程中要记录前驱节点，以便插入新节点时使用
时间复杂度O(n)

public ListNode insertSortListNode(ListNode head, int item){
        ListNode node;
        if(head == null){
            node = new ListNode(item);
            return node;
        }
        node = new ListNode(item);
        //寻找插入位置,如果比头节点小，往前插
        if(item < head.val){
            node.next = head;
            head = node;
        }else{
            //往后找插入位置,同时记录pre为前驱节点
            ListNode cur = head;
            ListNode pre = head;
            while(cur!=null && item >= cur.val){
                pre = cur;
                cur = cur.next;
            }
            //插入节点
            node.next = cur;
            pre.next = node;
        }
        return head;
    }

2.6 删除链接中指定节点

思路：在查找过程中要记录前驱节点，以便删除节点时使用
时间复杂度O(n)

public ListNode deleteNode(ListNode head, int item){
        if(head == null){
            return head;
        }
        ListNode cur;
        if(head.val == item){
            //先设置在赋值为null
            cur = head.next;
            head.next = null;
            return cur;
        }else{
            //往后找节点,同时记录pre为前驱节点
            cur = head;
            ListNode pre = head;
            while (cur!=null && item != cur.val){
                pre = cur;
                cur = cur.next;
            }
            //如果不为null，证明找到了该节点，删除节点
            if(cur != null){
                pre.next = cur.next;
                cur.next = null;
            }
        }
        return head;
    }

2.7 逆转链表

public ListNode invert(ListNode head){
        //pre指针, 上一个节点，刚开始为空
        ListNode pre = null;
        //遍历指针
        ListNode cur = head;
        //copy指针, 用来反向连接上一个节点pre
        ListNode copyCur = null;
        while (cur!=null){
            pre = copyCur;
            copyCur = cur;
            cur = cur.next;
            copyCur.next = pre;
        }
        head = copyCur;
        return head;
    }

• ← Previous Post
• Next Post →