力扣刷题八月第一天

奇偶链表

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

示例 1:

输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]

示例 2:

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

/**
 * 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; }
 * }
 */
 /*
 首先我们将一个链表分成两条，一条记录奇数，一条记录偶数，然后将其和并即可，我们将奇数的头指针标记为a，将偶数的头指针标记为b，然后用bhead保持指向偶数链表的头以便于最后合并链表,循环中的判断中的b一定不可以换成a,因为循环结束后a一定是不可以指向空节点的，这样会导致奇数链表的尾部指针丢失，而偶数指针在奇数指针后面，所以只需要保证b或者b.next不为空即可
  */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
        return head;
    }
    ListNode a = head, b = head.next, bHead = b;
    while (b != null && b.next != null) {
        a.next = a.next.next;
        a = a.next;
        b.next = b.next.next;
        b = b.next;
    }
    a.next = bHead;
    return head;
    }
}

1374、生成每种字符都是奇数个的字符串

给你一个整数 n，请你返回一个含 n 个字符的字符串，其中每种字符在该字符串中都恰好出现 奇数次 。

返回的字符串必须只含小写英文字母。如果存在多个满足题目要求的字符串，则返回其中任意一个即可。

示例 1：

输入：n = 4
输出："pppz"
解释："pppz" 是一个满足题目要求的字符串，因为 'p' 出现 3 次，且 'z' 出现 1 次。当然，还有很多其他字符串也满足题目要求，比如："ohhh" 和 "love"。

示例 2：

输入：n = 2
输出："xy"
解释："xy" 是一个满足题目要求的字符串，因为 'x' 和 'y' 各出现 1 次。当然，还有很多其他字符串也满足题目要求，比如："ag" 和 "ur"。

示例 3：

输入：n = 7
输出："holasss"

class Solution {
    public String generateTheString(int n) {
        /**
        判断n是奇数还是偶数，如果是奇数，直接拼接n个字符；如果是偶数，拼接n-1个字符，之后再拼接一个另外的字符。
         */
        StringBuilder str = new StringBuilder();
        if(n % 2 == 0){
            for(int i = 0;i< n - 1;i++){
                str.append('s');
            }
                str.append('b');
        }else{
            for(int i = 0;i < n;i++){
                str.append('s');
            }
        }
        return str.toString();
    }
}

剑指 Offer 52. 两个链表的第一个公共节点

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
        让两个链表的节点一起走，当某一个走到链表的尾部时，指向另一个链表的头部继续遍历。
        如果两个链表长度不同，当两个链表的指针都分别指向了对方的头指针时，继续往下走，直到走到公共结点的位置。
         */
        ListNode p1 = headA;
        ListNode p2 = headB;
        while(p1!=p2){
            p1 = (p1==null) ? headB : p1.next;
            p2 = (p2==null) ? headA : p2.next;
        }
        return p1;
    }
}