反转链表

反转一个单链表

示例：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解析(1):递归

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

解析(2):非递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next ==null){
            return head;
        }
        ListNode p = head.next;//1-2-3-4-5-null中2
        ListNode q = p.next;//1-2-3-4-5-null中3
        ListNode t = null;//设为null，避免野指针问题
        p.next = head;//直接将2指向1
        head.next = null;//1的后继变为null，即变为尾节点
        while(q != null){//q不为空就一直执行后面的节点指向前面节点
            t =q.next;
            q.next = p;
            p = q;
            q = t;
        }
        return p; 
    }
}

两两交换链表中的节点

示例:

输入: 1->2->3->4->NULL
输出: 2->1->4->3->NULL

解析：

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;//哑节点
        ListNode temp = pre;//记录pre的位置
        while(temp.next != null && temp.next.next != null) {//必须是两两节点，否则的话最后一个单节点直接输出
            ListNode start = temp.next;//记录1
            ListNode end = temp.next.next;//记录2
            temp.next = end;//temp指向2
            start.next = end.next;//1指向3
            end.next = start;//2指向1
            temp = start;//现在的temp在3处
        }
        return pre.next;
    }
}