笔试总结--链表操作

约定不等于承诺〃 2022-05-18 08:14 155阅读 0赞

### 1.输入一个链表，输出该链表中倒数第k个结点。 ###

//链表节点类
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }

##### 最简单粗暴一点的方法：先遍历一次，得到链表长度l，再遍历一次，遍历到l-k+1处的节点即为所求 #####

public class Solution {
        public ListNode FindKthToTail(ListNode head,int k) {
            int length = 1;
            ListNode node = head;
            if(head == null)
                return null;
            while(node.next != null){
                length ++;
                node = node.next;
            }
            if(k > length || k <= 0)
                return null;
            int count = 1;
            node = head;
            while(node.next != null){
                if(count == length - k + 1)
                    return node;
                else{
                    node = node.next;
                    count++;
                }
            }
            return node;
        }
    }

##### 比较聪明一点的算法是使用两个指针，先将第一个指针移动k-1步，然后两个指针同时移动，当第一个指针移动到链表结尾时，第二个指针的位置就是倒数第k个节点。如此只需遍历一遍。 #####

public class Solution {
        public ListNode FindKthToTail(ListNode head,int k) {
            ListNode p1 = head;
            ListNode p2 = head;
            if(head == null || k <= 0)
                return null;
            //先将第一个指针移动k-1步
            for(int i = 1; i < k; i++){
                p1 = p1.next;
                if(p1 == null)
                    return null;
            }
            while(p1.next != null){
                p1 = p1.next;
                p2 = p2.next;
            }
            return p2;
        }
    }

### 2. 输入一个链表，反转链表后，输出新链表的表头。 ###

##### 改变指针指向，向后改为向前即可，无需新建链表，节省空间。 #####

public class Solution {
        public ListNode ReverseList(ListNode head) {
            ListNode current = head;
            ListNode pre = null;
            ListNode next = null;
            while(current != null){
                next = current.next;
                current.next = pre;
                pre = current;
                current = next;
            }
            return pre;
        }
    }

### 3. 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 ###

##### 参考归并排序算法，比较两个链表节点值大小，将小的插入新链表中，并将链表向后移动一位。当有某一个链表达到结尾时，将另一个链表剩下的一次性全部插入新链表中。 #####

public class Solution {
        public ListNode Merge(ListNode list1,ListNode list2) {
            if(list1 == null)
                return list2;
            if(list2 == null)
                return list1;
            ListNode mergeHead = null;
            ListNode current = null;     
            while(list1!=null && list2!=null){
                if(list1.val <= list2.val){
                    if(mergeHead == null){
                        mergeHead = current = list1;
                        list1 = list1.next;
                    }else{
                             current.next = list1;
                             current = current.next;
                             list1 = list1.next;
                         }
                 }else{
                        if(mergeHead == null){
                        mergeHead = current = list2;
                        list2 = list2.next;
                    }else{
                            current.next = list2;
                            current = current.next;
                            list2 = list2.next;
                          }
                      }
                  }
             if(list1 == null){
                  current.next = list2;
             }else{
                  current.next = list1;
                  }
             return mergeHead;
        }
    }