Linked-List相关

[Reversed-LinkedList] https://leetcode.com/problems/reverse-linked-list/description/
1.Reversed Linked-list

class Solution {
   public ListNode reverseList(ListNode head) {
       ListNode prev = null;       
       while (head != null) {
           ListNode temp = head.next;
           head.next = prev;
           prev = head;
           head = temp;
       }
       return prev;      
   }
}

2.[Reversed Linked List II]https://leetcode.com/problems/reverse-linked-list-ii/description/
solution：重点是找到需要翻转的区间，具体看注释

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) {
            return null;
        }
        
        ListNode dummy = new ListNode(0);// create a dummy node to mark the head of this list
        dummy.next = head;
        ListNode pre = dummy;// make a pointer pre as a marker for the node before reversing
        
        for (int i=0; i<m-1; i++) {
            pre = pre.next;
        }
        ListNode start = pre.next;// a pointer to the beginning of a sub-list that will be reversed
        ListNode tail = start.next;// a pointer to a node that will be reversed
        
        // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, tail = 3
        // dummy-> 1 -> 2 -> 3 -> 4 -> 5
        
        for (int i=0; i<n-m; i++) {
            start.next = tail.next;
            tail.next = pre.next;
            pre.next = tail;
            tail = start.next;
            //this phase is the standard code for reverse Linked List,need to be one-to-one correspondence
        }
        return dummy.next;        
    }
}

3.判断链表是否有环
[Linked List Cycle] https://leetcode.com/problems/linked-list-cycle/description/

solution：快慢指针

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            if (fast.next == null) {
                return false;
            }
            if (fase.next == slow) {
                return true;
            }
        }
        fast = fast.next.next;
        slow = slow.next;       
    }
    return false;
}

4.删除链表倒数第N个节点
[Remove Nth Node form End of LinkedList]https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
solution:快慢指针，看注释

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode(0);
        ListNode slow = start, fast = start;
        slow.next = head;        
        //将fast先走，与slow的距离保证为n
        for (int i=1; i<=n+1; i++) {
            fast = fast.next;
        }        
        //将fast走到头，然后slow走到中间，两者的距离正好还是n
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }        
        //删除目标节点
        slow.next = slow.next.next;
        return start.next;        
    }
}

5.删除链表中的元素
[Remove Linked List Elements]https://leetcode.com/problems/remove-linked-list-elements/description/
solution:链表删除的统一做法，要注意找到删除节点的前一个节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        
        while (head.next != null) {
            if (head.next.val == val) {
                head.next = head.next.next;
            } else {
                head = head.next;//move head pointer to next and then loop
            }
        }
        return dummy.next;
    }
}

6.两个链表第一个公共节点
solution：首先遍历两个链表得到它们的长度，就知道哪个链表比较长，以及它的链表比断的链表多几个节点。在第二次遍历的时候，在较长的链表上先走若干步，接着再同时在两个链表上遍历，找到第一个相同的节点就是它们的第一个公共节点。

public ListNode findFirstCommonNode (ListNode pHead1, ListNode pHead2) {
    if (pHead1 == null || pHead2 == null) {
        return null;
    }

    //定义两个指针
    ListNode node1 = pHead1, node2 = pHead2;
    int length1 = 0, length2 = 0;
    //遍历两个链表
    while (node1 != null) {
        length1 += 1;
        node1 = node1.next;
    }
    while (node2 != null) {
        length2 += 1;
        node2 = node2.next;
    }
    //对较长链表的头结点处理，先走差值k步
    if (length1 > length2) {
        int k = length1 - length2;
        while (k != 0) {
            pHead1 = pHead1.next;
            k--;
        }       
    } else {
        int k = length2 - length1;
        while (k != 0) {
            pHead2 = pHead2.next;
            k--;
        }       
    }
    //遍历第一个相同的节点就是第一个公共节点
    while (pHead1 != pHead2) {
        pHead1 = pHead1.next;
        pHead2 = pHead2.next;
    }
    return pHead1;
}

7.从尾到头打印链表
solution：兼职offer版本，看代码

//栈的方式
class Solution {
    public static void printListReverse(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        if (head == null) {
            return;
        }
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        while (!stack.empty()) {
            stack.pop();
        }
    }
}


//递归的方式
class Solution {
    public staic void pinrtListReverse(ListNode head) {
        if (head == null) {
            return;
        }
        while (head != null) {
            if (head.next != null) {
                ListNode next = head.next;
                printListReverse(next);
            } else {
                return;
            }
        }
    }
}