leetcode-02（链表题）

 迭代法：

思路：划分一个局部位置，然后用一个辅助节点和辅助指针，比较大小然后辅助指针去连即可，每连一次位置往后推；

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  //辅助迭代法
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
      ListNode help=new ListNode(-1);
      ListNode pre=help;//辅助指针

      //遍历
       while (l1 != null && l2 != null){
        if(l1.val<=l2.val){
          //进行连接
          pre.next=l1;
          pre=pre.next;
          l1=l1.next;
        }else{
            pre.next=l2;
            pre=pre.next;
            l2=l2.next;
        }
      }
      //对剩下节点直接连
      if(l1!=null){
        pre.next=l1;
      }
      if(l2!=null){
        pre.next=l2;
      }
           
      return help.next;
    }
}

递归解法

class Solution {
  //递归
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //1.结束条件
    if(l1==null){
      return l2;
    }
    if(l2==null){
      return l1;
    }
    //2.递归思路
    if(l1.val<=l2.val){
      l1.next=mergeTwoLists(l1.next,l2);
      return l1;
    }else{
        l2.next=mergeTwoLists(l1,l2.next);
        return l2;
    } 

    
    }
}

 

递归解法，与上提类似

class Solution {
    //递归
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //1.结束条件
        if(list1==null){
         return list2;
        }
        if(list2==null){
         return list1;
        }

        //2.递归思路
        if(list1.val<=list2.val){
          list1.next=mergeTwoLists(list1.next,list2);
          return list1;
        }else{
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}

 

迭代法

注意指针的利用指向head，然后指向前一个结点，慢慢往后推

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
          ListNode pre=null;
          ListNode cur=head;
          //每次循环进行两两交换
          while(cur!=null){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
          }
          return pre;
    }

快慢指针：

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            ++n;
            cur = cur.next;
        }
        int k = 0;
        cur = head;
        while (k < n / 2) {
            ++k;
            cur = cur.next;
        }
        return cur;
    }
}